Finding the missing number in an array

Question

An array a[] contains all of the integers from 0 to N, except one. However, you cannot access an element with a single operation. Instead, you can call get(i, k) which returns the kth bit of a[i] or you can call swap(i, j) which swaps the ith and jth elements of a[]. Design a O(N) algorithm to find the missing integer. (For simplicity, assume N is a power of 2.)

• Karoly Horvath: is this homework? what have you tried?
• Karoly Horvath: also: O(N)? It should depend on the number of bits, right?
• Ivan Koblik: I saw this question on careercup.com could be from an interview. EDIT: It's marked homework, still that one can be asked on an interview...
• Sap: do the addition of 1 to n (which is n(n+1)/2) then figure out to find addtion of given array and subtract both. That is your missing numbner time complexity o(n)
• gaganbm: Are the array elements sequential ? Or they are randomly present in the array ??

Answer 1

If N is a power of 2, it can be done in O(N) using divide and conquer.

Note that there are logN bits in the numbers. Now, using this information - you can use a combination of partition based selection algorithm and radix-sort.

1. Iterate the numbers for the first bit, and divide the array to two halves - the first half has this bit as 0, the other half has it as 1. (Use the swap() for partitioning the array).
2. Note that one half has ceil(N/2) elements, and the other has floor(N/2) elements.
3. Repeat the process for the smaller array, until you find the missing number.

The complexity of this approach will be N + N/2 + N/4 + ... + 1 < 2N, so it is O(n)

• iloahz: good answer, karoly was close to this but ignored some extra information from the queries.
• amit: Yeap, it is actually an upgrade for his (good) answer, using the same approach - but reducing the problem as we go on, using the swap() functionality provided.

Answer 2

O(N*M), where M is the number of bits:

N is a power of 2, only one number is missing, so if you check each bit, and count the numbers where that bit is 0, and count where is 1, you'll get 2^(M-1) and 2^(M-1)-1, the shorter one belongs to the missing number. With this, you can get all the bits of the missing number.

• amit: Note that M = O(logN) - since the numbers are in range [0,N), so you can bound it as function of N alone.

Answer 3

there are really no even need to use swap operation!! Use XOR! Okay, first you can calculate binary XOR of all number from 0 to N. So first:

long nxor = 0;
for (long i = 0; i <= N; i++)
 nxor = XOR(nxor, i);

Then we can calculate XOR of all numbers in array, it's also simple. Let's call as K - maximal number of bits inside all number.

long axor = 0;
long K = 0;
long H = N;
while (H > 0)
{
 H >>= 1; K++;
}
for (long i = 0; i < N - 1; i++)
 for (long j = 0; j < K; k++)
 axor = XOR(axor, get(i,j) << j);

Finally you can calculate XOR of result:

long result = XOR(nxor, axor).

And by the way, if n is a power of 2, then nxor value will be equal to n ;-)!

• amit: Note that K is O(logN) (or Omega(logN) to be exact), thus the solution is O(NlogN)
• Avi Cohen: Also, you can not access a number as a whole, just its bits.
• Gloomcore: I do not access numbers from array. But N number is known anyway)So precalculate XOR operation - is possible for this task
• Gloomcore: With divide and conquer I can give better solution but it's complexity anyway will be O(n log(log n)), which unfortunantly is bigger than O(n)
• amit: @Gloomcore: There is a divide&conquer O(N) solution, have a look at my answer and complexity analysis for it.

Answer 4

Suppose that the input is a[]=0,1,2,3,4,5,7,8, so that 6 is missing. The numbers are sorted for convenience only, because they don't have to be sorted for the solution to work.

Since N is 8 then the numbers are represented using 4 bits. From 0000 to 1000.

First partition the array using the most significant bit.

You get 0,1,2,3,4,5,7 and 8. Since 8 is present, continue with the left partition.

Partition the sub array using the 2nd most significant bit.

You get 0,1,2,3 and 4,5,7. Now continue with the partition that has odd number of elements, which is 4,5,7.

Partition the sub array using the 3rd most significant bit.

You get 4,5 and 7. Again continue with the partition that has odd number of elements, which is 7.

Partition the sub array using the 4th most significant bit you get nothing and 7.

So the missing number is 6.

Another example:

• a[]=0,1,3,4,5,6,7,8, so that 2 is missing.
• 1st bit partition: 0,1,3,4,5,6,7 and 8, continue with 0,1,3,4,5,6,7.
• 2nd bit partition: 0,1,3 and 4,5,6,7, continue with 0,1,3 (odd number of elements).
• 3rd bit partition: 0,1 and 3, continue with 3 (odd number of elements).
• 4th bit partition: nothing and 3, so 2 is missing.

Another example:

• a[]=1,2,3,4,5,6,7,8, so that 0 is missing.
• 1st bit partition: 1,2,3,4,5,6,7 and 8, continue with 1,2,3,4,5,6,7.
• 2nd bit partition: 1,2,3 and 4,5,6,7, continue with 1,2,3 (odd number of elements).
• 3rd bit partition: 1 and 2,3, continue with 1 (odd number of elements).
• 4th bit partition: nothing and 1, so 0 is missing.

The 1st partition takes N operations. The 2nd partition takes N operations. The 3rd partition takes N/2 operations. The 4th partition takes N/4 operations. And so on.

So the running time is O(N+N+N/2+N/4+...)=O(N).

Answer 5

And also you another anwer when we will use sum operation instead of xor operation. Just below please find code.

long allsum = n * (n + 1) / 2;
long sum = 0;
long K = 0;
long H = N;
while (H > 0)
{
 H >>= 1; K++;
}
for (long i = 0; i < N - 1; i++)
 for (long j = 0; j < K; k++)
 sum += get(i,j) << j;
long result = allsum - sum.

Answer 6

With out xor operation, we will answer this question like this way

package missingnumberinarray;
public class MissingNumber 
{
 public static void main(String args[])
 {
 int array1[] = {1,2,3,4,6,7,8,9,10}; // we need sort the array first.
 System.out.println(array1[array1.length-1]);
 int n = array1[array1.length-1];
 int total = (n*(n+1))/2;
 System.out.println(total);
 int arraysum = 0;
 for(int i = 0; i < array1.length; i++)
 {
 arraysum += array1[i];
 }
 System.out.println(arraysum);
 int mis = total-arraysum;
 System.out.println("The missing number in array is "+mis);
 }
}