Matrix Matching

You are given 3 parameters: int U, int L, and array C containing n ints. Find a matrix with 2 rows and n columns where:
– Each element is either 1 or 0.
– The sum of ints in the upper row is U.
– The sum of ints in the lower row is L.
– C is an array of ints of length n, where the sum of ints in k-th column is C[k].

Convert each matching matrix to a comma separated string and return them in an array. If there is no match, return “IMPOSSIBLE”.

For example, given:

U = 2
L = 2
C = [2, 0, 2, 0]

Its only valid matrix and result is:

1  0  1  0
1  0  1  0

[ "1010,1010" ]

To solve, simply increment through ints, convert them to binary arrays, and compare sums. Since C is of length n, the range of numbers to check is 0 to 2^n – 1.

function solution(U, L, C) {
  const max = Math.pow(2, C.length)
  const matches = []

  for (let upper = 0; upper < max; upper++) {
    let upperArray = intToBinaryArray(upper, C.length)

    if (!isBitSumEqual(upperArray, U))
      continue

    for (let lower = 0; lower < max; lower++) {
      let lowerArray = intToBinaryArray(lower, C.length)

      if (!isBitSumEqual(lowerArray, L))
        continue

      if (isMatch(upperArray, lowerArray, U, L, C))
        matches.push(${upperArray.join("")},${lowerArray.join("")})
    }
  }

  if (matches.length > 0)
    return matches

  return "IMPOSSIBLE"
}

function isMatch(upperArray, lowerArray, U, L, C) {
  for (let i = 0; i < C.length; i++) {
    let u = upperArray[i]
    let l = lowerArray[i]
    let c = C[i]

    if (u + l != c)
      return false
  }

  if (!isBitSumEqual(upperArray, U))
    return false

  if (!isBitSumEqual(lowerArray, L))
    return false

  return true
}

function isBitSumEqual(array, sum) {
  let total = 0

  for (let i = 0; i < array.length; i++) {
    total += array[i]
  }

  return (total == sum)
}

function intToBinaryArray(n, length) {
  let binary = n.toString(2)
  let binaryPadded = binary.padStart(length, '0')
  let binStringArray = binaryPadded.split("")
  let binIntArray = binStringArray.map(Number)
  return binIntArray
}

let U = 2
let L = 2
let C = [2,0,2,0]

console.log(U: ${U} L: ${L} C: ${C})
let result = solution(U, L, C)
console.log(result)

U = 3
L = 2
C = [2,1,1,0,1]

console.log(U: ${U} L: ${L} C: ${C})
result = solution(U, L, C)
console.log(result)


U: 2 L: 2 C: 2,0,2,0
[ '1010,1010' ]
U: 3 L: 2 C: 2,1,1,0,1
[ '10101,11000', '11001,10100', '11100,10001' ]