Find missing number in bit array

Question

This problem is taken directly from Cracking the Coding Interview, 4th Ed, so I'm not 100% sure I can post it here; if not, just let me know and I'll delete this.

Question 5.7:

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?

I know how to solve this. What I don't understand, is how she solved it. Her method:

1. Start with least sig bit.
2. Count occurrence of 1's vs 0's.
3. If count(1) < count(0) => the missing number has a 1 as it's least sig bit, else it has a 0.
4. Remove all numbers with least sig bit not matching result found in step 3.
5. Repeat steps 1->4, iterating from least sig bit -> 2nd least sig bit -> ... -> most sig bit

I can see this working when n is of the form (2^m)-1 for some positive m... but don't see how it would work in the general case.

Consider the natural numbers in binary radix. Then the sequence of the ith-least sig bit goes like:

1. 0,1,0,1,0,1,0,... = {01}* = {(1)0(1)1}*
2. 0,0,1,1,0,0,1,1,... = {0011}* = {(2)0(2)1}*
3. 0,0,0,1,1,1,0,0,0,... = {000111}* = {(3)0(3)1}*

Then the most sig bit has some sequence {(s)0(s)1} for some s. If n=(2^m)-1, then all is well; for each magnitude, the #1s = #0's and thus we can use the authors logic. But, how does this work in the general case? If n is some arbitrary number, the sequence of most-sig bits leading up to n looks like: (s)0(s)1(s)0(s)1...(k)1 (clearly the sequence must end with 1 as most sig bit), and k could be any number in [0,s]. So how does her logic apply? (Most notably, step 3 assumes that #0's is at most 1 more than #1's in the usual case)

Thanks if anyone could shed some light on this! Thanks!

Answer 1

There are 3 possibilities:

1. n is odd, so the number of 0 bits and 1 bits should be the same. They won't be, so the lower number is obviously the missing one.
2. n is even, so the number of 0 bits should be 1 greater than the number of 1 bits. If they're equal, it's the 0 bit that's missing.
3. As above, n is even. If the number of 0 bits is 2 greater than the number of 1 bits, the 1 bit is the missing one.

By removing all the numbers that have been eliminated, you're now applying the exact same problem again, recursively.