Report all missing numbers in an array of integers (represented in binary)

I recently had a friend report to me that during a job interview he was asked th开发者_开发百科e following question, which seems to be a pretty popular one:

You are given a list L[1...n] that contains all the elements from 0 to n except one. The elements of this list are represented in binary and are not given in any particular order, and the only operation we can use to access them is to fetch the jth bit of L[i] in constant time. How can you find the missing number in O(n) ?

He was able to answer this question (which I believe has multiple solutions, none of which being too complicated). For example, the following pseudo-code solves the above problem:

Say all numbers are represented by k bits and set j as the least significant bit (initially the rightmost).

1. Starting from j, separate all the numbers in L into two sets (S1 containing all numbers that have 1 as its jth bit, and S2 containing all numbers that have 0 in that position).

2. The smaller of the two sets contains the missing number, recurse on this subset and set j = j-1

At each iteration we reduce the size of the set by half. So initially we have O(n), followed by O(n/2), O(n/4) ... = O(n)

However the follow-up question was: "What if we now have k numbers missing in our list L and we wish to report all k numbers while still keeping the O(n) complexity and the limitations of the initial problem? How to do?

Any suggestions?

bool J[1..n + 1]={false,false...}
int temp;

for(i = 1; i <= n; i++)
{
    temp=bitwisecopy of L[i];
    J[temp + 1]=true
}

for(i = 1; i <= n+1; i++)
{
    if(J[i]==false)
       print i + 1;
}

Lol thats the jist of it...I think indices may be messed up.

Am I understanding the problem correctly? It wasn't all the clear to me what exactly was meant by the only operation is access the jth bit of L[i].

You can solve the original problem in O(n) by just doing a linear walk of the array until you find a number that doesn't match the expected value, like so (yes, I know I'm using an array of ints to approximate the array of bits, but the concept is the same):

int[] bits = {1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0};
int bitIndex = 0;
for (int num = 1; num < Integer.MAX_VALUE; num++) {
    int numBits = (int) (Math.log(num) / Math.log(2)) + 1;
    int nextNum = 0;
    for (int index = 0; index < numBits; index++) {
        nextNum = (nextNum << 1) | bits[bitIndex + index]; 
    }
    if (nextNum != num) {
        System.out.println("Missing number:  expected=" + num + ", actual=" + nextNum);
        break;
    }

    bitIndex += numBits;
}

If you want to print all of the numbers that are not present in the array while keeping O(n) runtime, just replace the break; with num = nextNum; to continue checking for the next number.

Though there are some potential problems with this approach. If multiple consecutive numbers are missing then all bets are off. Also if the number of bits in num + 1 is larger than the number of bits in num, and num is missing from the bit array, then the bit index will be out of alignment with the data.

Of course, if multiple numbers are allowed to be missing, then the problem isn't really solvable. Consider for example:

{1,1,1,1,1,1,1}

It's just as valid in this case to say that I have numbers 1, 3, and 15 as it is to say that I only have 127 or that I have 7 and 15. When multiple consecutive values are permitted to go missing, the way to parse the bits essentially becomes arbitrary.

So perhaps one way to answer the second question is to read all the bits into a single large integer, and say "you have [very large number], and all the numbers before it are missing". Then you've produced a valid answer in O(n) time.

My idea is to solve it in the following way:

lets say 2^M is the lowest power of 2 that higher than N:

2^M>N,    2^M-1 <= N

now go over all the numbers from 1 to 2^M-1 and do bitwise XOR between all the numbers (since you can only go over bit J each time do it for each digis separately - it's the same)

the result of all the XORs will be the number you are looking for.

for example: if N=6, and the missing number is 3:

M=3 => 2^M-1=7 =>
1 XOR 2 XOR 4 XOR 5 XOR 6 XOR 7 = 3