Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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)$.

share|cite|improve this answer

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.
   var currentBit = A[index].bit(0)
   if(currentBit == previousBit)
       previousBit = currentBit

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.