CODEWITHSUNDEEP
algorithm
Raj
Raj

Reputation: 4462

Finding the missing number in an array

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

Upvotes: 2

Views: 5465

Answers (6)

ravi
ravi

Reputation: 1

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);
    }
}

Upvotes: 0

Gloomcore
Gloomcore

Reputation: 950

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.

Upvotes: 0

Avi Cohen
Avi Cohen

Reputation: 3414

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

Upvotes: 0

Gloomcore
Gloomcore

Reputation: 950

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 ;-)!

Upvotes: 1

amit
amit

Reputation: 178491

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)

Upvotes: 9

Karoly Horvath
Karoly Horvath

Reputation: 96286

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.

Upvotes: 3

Related Questions