Removing even/odd numbers to find missing number in an array of array of numbers represented in binary

Question

This is related to problem 5.7 (under Bit Manipulation) in the 5th edition of Cracking the coding interview (if the is question is not appropriate for SO, please let me know the correct site and I'll move it):

An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single opera-tion. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

The algorithm applied is this:

1. Check LSBs of all numbers in the list.
2. Count occurrence of 1's and 0's in the LSBs. If count(0)<=count(1), the LSB of the missing number is 0. Else it is 1.
3. Remove all numbers with LSB not matching result found in step 2.
4. Repeat 1 to 4, and progressively check the next LSB in each iteration.

Can someone explain the logic behind step 3? It basically removes all odd/even numbers from the current list (depending on the bit found for the missing number) and uses the modified list in the next iteration. Why do we do this?

Answer 1

The algorithm does not work. If the number of elements in the array is even, then step 2 may find an equal number of 0s and 1s. This can happen, for example, when the missing number is at one end or the other of the range.

If the number of elements in the array is not even, it will be on the next iteration after step 3.

ADDENDUM

Here is an example.

Set: 0, 1, 3

After step 1&2, we have 1 LSB=0 and 2 LSB=1. So, according to step 2, the LSB must be 0. So far, so good.

After step 3, removing values from the set with LBS=1 we have:

Set: 0

After step 1&2, we have 1 LSB'=0 and 0 LSB'=1. So, according to step 2, the LSB' must be 1.

At this point we're done (the set is empty after removing elements with LSB'=0), and have identified 2 as the answer (LSB' = 1, LBS = 0).

How does this work?

After every iteration, think about shifting the values in the array right by one bit to discard the bit determined in the previous iteration. This will create duplicates in the array for all values except the missing one. The algorithm is simply throwing away these duplicates.

Answer 2

Step 3 is meant to (vastly) improve the runtime of the algorithm. If step 3 is included, then the overall algorithm is a binary search algorithm using the LSB as the branching decider. If step 3 is omitted, then it is still a binary search, but one that is implemented in a way that does not become logarithmically faster on each pass (which will exceed the O(n) bound).

Incidentally, as written it seems like there's a bit shift missing, or the term LSB is being used in a rather liberal way.