Find Missing row in n*2^n matrix in 2^n time Algorithm question

Question

I encountered an Algorithms question which seemed easy at first but I'm puzzled and don't know what to do! the question is as follows:

Suppose we have a number n, and then we have a matrix of n columns and 2*n rows. it is like the power set (e.g. for n=2 we have 10,11,00,01). the rows don't necessarily follow any order. also we can access each matrix member in O(1) time. now, we have (2^n)-1 of the rows, and we want to find the last row in least possible time (note that there are n*(2^n-1) members and we only have O(2^n) time). how can we do this? (we have O(n) memory. though I'm not sure if it's enough. if you know an answer which uses any amount of memory it's fine)

Example input:

3
101
110
100
000
111
011
010

Example output: 001

I tried to model it by the popular missing bit problem (by xor-ing the matrix members) but couldn't do much progress.

P.S. an implementation of the algorithm on C/C++/Java/Python will be very appreciated as it clarifies things up.

P.S.S: Can you also cite some sources? or tell me how you came up with the answer and how you think about such questions?

Answer 1

The constraints are a little vague, but you're probably looking for something like this:

• Check the first item in all 2^n rows to determine the first item in the missing row. Either 1 or zero will start 2^(n-1) rows, and the other option will start 2^(n-1)-1 rows -- item with the lower count starts the missing row.
• Check the second item in the 2^(n-1)-1 rows that start with the same item as the missing row, to find the second item in the missing row.
• Continue to find all n items in the missing row.

If you sum up the number of elements read you get 2^n + 2^(n-1) + 2^(n-2) ... which is less than 2^(n+1) and therefore in O(2^n)

Answer 2

You have 2 cases here:

1. Degenerated case: N == 1 which is evident. 0 -> 1 and 1 -> 0; you can, say, put it as ~item

2. General case N > 1. All you have to do is to xor all the values:

   101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001

the algorithm has O(N * 2**N) time complexity (we have to read each cell of the matrix) and wants O(n) space (to store temporal sum when xoring).

C# implementation (Linq):

  string source = "3 101 110 100 000 111 011 010";

  // "001"
  // new char[] { ' ', '\r', '\n', 't' } - to be on the safe side -
  // whatever delimiter is we'll get a correct array
  string result = source
    .Split(new char[] { ' ', '\r', '\n', 't' }, StringSplitOptions.RemoveEmptyEntries)
    .Skip(1) // we don't want "3"
    .Aggregate((sum, item) =>  // xoring strings
       string.Concat(sum.Zip(item, (x, y) => (char)((x - '0') ^ (y - '0') + '0'))));

Let's prove algorithm's correctness (N > 1).

Since N > 1 and thus 2**N >= 4 then 2**(N - 1) is some even value. Let's have a look at arbitrary bit of all 2**N items of the power serie

 000...0...0
 000...0...1
  ...
 111.......0
 111...1...1
       ^
     - N/2 '0's (even) and N/2 '1' (even), xor == 0

we find that we have exactly N / 2 zeroes and N / 2 ones; xor of all these bits is aways 0 (since N / 2 == 2**(N - 1) is some even value). If one line is missed, e.g. 0...1...1 we have 2 possibilities:

1. Missed bit is 1. So we have N / 2 zeroes and N / 2 - 1 ones; xor of all bits returns 1
2. Missed bit is 0. So we have N / 2 - 1 zeroes and N / 2 - 1 ones; xor of all bits returns 1

Since ^ is a bitwise operation (value of jth bit doesn't depend on values of ith bits) and we prove that arbitrary bit is correct one the entire value is correct as well.