Tricky algorithm question

Question

Possible Duplicate:
Quickest way to find missing number in an array of numbers

Input: unsorted array A[1,..,n] which contains all but one of the integers in the range 0,..,n

The problem is to determine the missing integer in O(n) time. Each element of A is represented in binary, and the only operation available is the function bit(i, j), which returns the value of the jth bit of A[i] and takes constant time.

Any ideas? I think some sort of divide-and-conquer algorithm would be proper, but I can't think of what exactly I should do. Thanks in advance!

Answer 1

It's a mathematical property that the sum of the numbers between 1 and n where n is n(n+1)/2. You can see this for 10:

  1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6)
= 11 + 11 + 11 + 11 + 11
= 55

So, by extension, is the sum of the numbers from 0 thru n since you're just adding 0 to it. So what you do is add up all the numbers and maintain a count, then use that formula to figure out the missing one.

So, something like:

count = 0
sum = 0
foreach num in list:
    sum = sum + num
    count = count + 1
missing = count * (count+1) / 2 - sum

Getting the number with bit(i,j) is tricky so you'll have to extract the bits individually and turn them into actual numbers for summing.

Answer 2

It's a trick question then, since using the bit method would only require that you cycle each bit for each number, meaning it would automatically become O(n*j) where j is the number of bits representing n.

I think paxdiablo's got it, assuming you're allowed a solution which doesn't use the bit method.

Answer 3

You could use XOR operator as its faster than addition. Since you have access to each bit you will be doing a bitwise XOR here. The principle to be used here is (A XOR B XOR A ) = B

eg: (1 XOR 2 XOR 3) XOR (1 XOR 2) = 3

for i=0 to n
{
Total=Total XOR i
}

foreach element in A
{
Total=Total XOR element
}