Hints

Solve it for a binary array, i.e a[i] is either 0 or 1.

Solve an even easier version first. For the binary array above, say I give you a hint that a[i*] = 0. Is it now easy to find the solution?

Since the array elements are either 0 or 1, and 0 | 0 = 0 and 0 | 1 = 1, hence, 0 | x = x. Hence, if you were to look at the i* row, the entries would be something like

a[i*] | a[j] = 0 | a[j] = a[j]

Hence, you should be able to compute the entire array with just this one hint.

Now, what if I don’t give you the initial hint that a[i*] = 0. Can you smartly figure out such an i*?

Locate any zero in the matrix. When can a zero occur? Whata does it mean when you can’t locate a zero?

If you can’t locate any zero, does that mean the original array contained all ones?

No, it’s not ALWAYS true that all 1s in the matrix implies that all elements in the original array were 1.

There could be at max one zero in the array.

For example, [1, 1, 1] and [1, 0, 1] have the same matrix.

Since the problem asks us to print any array, we should be fine with assuming that all elements are 1. Note that this is one of the solution, not the only solution.

So, we’ve handled the case where you don’t find any 0 in the matrix. So, now, we know that there is atleast one 0, say, mat[i][j]? What does that tell us?

a[i] | a[j] = 0 implies that BOTH a[i] and a[j] are 0. We were able to successfully locate, not one, but two 0s. Voila, instead of relying on someone else for the hint of i*, we created our own hint. We know that the row corresponding to i* is the answer.

Now, how to solve this if the array is not a binary array?

Solve for each bit independently and final verify the answer by recreating the matrix.