Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|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 at 18:09

2 Answers 2

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|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.
   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.

share|improve this answer
    
The numbers aren't in sorted order. –  NightRa May 18 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 at 9:45

Your Answer

 
discard

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.