# Find The missing number in range [0,n]

Given Array A of size n that contains all the integer values $[0,n]$ except one.

In this question we assume that the time we need to check one bit $j$ in number $A[i]$ is $O(1)$,and to check the number $A[i]$ is $O(\log n)$.

Find an algorithm that finds the missing number in $O(n)$.

So creating a trivial counter array and searching for a 0 count wouldn't help - it would be $O(\log n)$.

I also thought about counting the bits and finding the missing one, but that wouldn't help either.

-
Can you clarify what u meant by "counting the bits and finding the missing one" - is it the same solution I outlined? – TCSGrad May 17 '14 at 18:09

Compare all the Least Significant bits, and either there are less ones or zeroes.

We continue this search only on the set where there is less of some bit, half the input at each iteration.

$$n + \frac{1}{2}n + \frac{1}{4}n + ... < 2n.$$

And we accumulate the missing bits at each step, to come to the missing number.

So the running time is $O(n)$.

-

Perhaps I am missing the point but this seems trivial.

var previousBit = 1;

for index = 0 to n -1 // -1 because the array is one short of n.
begin
var currentBit = A[index].bit(0)
if(currentBit == previousBit)
break;
else
previousBit = currentBit
end

print "missing number is ", index


Assuming A[index].bit(0) gives the zero-th bit of the number at the array position index.

This is plainly O(n)

This would be based on the observation that the least significant bit of the number toggles as you increase from 0 to n, and where it doesn't you have found the missing number.

-
The numbers aren't in sorted order. – NightRa May 18 '14 at 8:40
If they were, we could do a binary search, comparing the current element with the expected number, and if there was a shift, search where appropriate. – NightRa May 18 '14 at 9:45