Find the missing number in a group {0......2^k -1} range

Question

Given an array that has the numbers {0......2^k -1} except for one number , find a good algorithm that finds the missing number.

Please notice , you can only use :

• for A[i] return the value of bit j.

• swap A[i] with A[j].

My answer : use divide & conquer , check the bit number K of all the numbers , if the K bit (now we're on the LSB) is 0 then move the number to the left side, if the K bit is 1 then move the number to the right side. After the 1st iteration , we'd have two groups , where one of them is bigger than the other , so we continue to do the same thing, with the smaller group , and I think that I need to check the K-1 bit this time.

But from some reason I've tried with 8 numbers , from 0.....7 , and removed 4 (say that I want to find out that 4 is the missing number) , however to algorithm didn't work out so good. So where is my mistake ?

Answer 1

I assume you can build xor bit function using get bit j.

The answer will be (xor of all numbers)

PROOF: a xor (2^k-1-a) = 2^k-1 (a and (2^k-1-a) will have different bits in first k positions).
Then 0 xor 1 xor ... xor 2^k-1 = (0 xor 2^k-1) xor (1 xor 2^k-2).... (2^(k-1) pairs) = 0.
if number n is missing the result will be n, because 0 xor 1 xor 2....xor n-1 xor n+1 xor ... = 0 xor 1 xor 2....xor n-1 xor n+1 xor ... xor n xor n = 0 xor n = n

EDIT: This will not work if k = 1.

Answer 2

Ron,

your solution is correct. This problem smells Quicksort, doesn't it ?

What you do with the Kth bit (all 0's to the left, 1's to the right) is a called a partition - you need to find the misplaced elements in pairs and swap them. It's the process used in Hoare's Selection and in Quicksort, with special element classification - no need to use a pivot element.

You forgot to tell in the problem statement how many elements there are in the array (2^k-2 or more), i.e. if repetitions are allowed.

If repetitions are not allowed, every partition will indeed be imbalanced by one element. The algorithm to use is an instance of Hoare's Selection (only partition the smallest halve). At every partition stage, the number of elements to be considered is halved, hence O(N) running time. This is optimal since every element needs to be known before the solution can be found.

[If repetitions are allowed, use modified Quicksort (recursively partition both halves) until you arrive at an empty half. The running time is probably O(N Lg(N)) then, but this needs to be checked.]

You say that the algorithm failed on your test case: you probably mis-implemented some detail.

An example:

Start with 5132670 (this is range {0..7})

After partitioning on bit weight=4 you get 0132|675

where the shortest half is 675 (this is range {4..7})

After partitioning on bit weight=2, you get 5|67

where the shortest half is 5 (this is range {4..5})

After partitioning on bit weight=1, you get |5

where the shortest half is empty (this is range {4}). Done.

Answer 3

for n just add them all and subtract the result from n*(n+1)/2
n*(n+1)/2 is sum of 1...n all numbers. If one of them is missing, then sum of those n-1 numbers will be n*(n+1)/2-missingNumber
Your answer is: n*(n+1)/2-missingNumber where n is 2^k-1