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

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... — Ivan Koblik
– Ivan Koblik, Commented Sep 13, 2012 at 9:34
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) — Sap
– Sap, Commented Sep 13, 2012 at 9:35
Are the array elements sequential ? Or they are randomly present in the array ?? — gaganbm
– gaganbm, Commented Sep 13, 2012 at 9:39

amit · Accepted Answer · 2012-09-13 10:34:02Z

9

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.

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).
Note that one half has ceil(N/2) elements, and the other has floor(N/2) elements.
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)

edited Sep 13, 2012 at 10:34

answered Sep 13, 2012 at 10:27

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

iloahz Over a year ago

good answer, karoly was close to this but ignored some extra information from the queries.

amit Over a year ago

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.

Karoly Horvath · Accepted Answer · 2012-09-13 09:30:31Z

3

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.

answered Sep 13, 2012 at 9:30

Karoly Horvath

96.7k11 gold badges123 silver badges181 bronze badges

1 Comment

amit Over a year ago

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

Gloomcore · Accepted Answer · 2012-09-13 11:22:04Z

1

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

answered Sep 13, 2012 at 11:22

Gloomcore

9507 silver badges11 bronze badges

5 Comments

amit Over a year ago

Note that K is O(logN) (or Omega(logN) to be exact), thus the solution is O(NlogN)

Avi Cohen Over a year ago

Also, you can not access a number as a whole, just its bits.

Gloomcore Over a year ago

I do not access numbers from array. But N number is known anyway)So precalculate XOR operation - is possible for this task

Gloomcore Over a year ago

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 Over a year ago

@Gloomcore: There is a divide&conquer O(N) solution, have a look at my answer and complexity analysis for it.

Avi Cohen · Accepted Answer · 2012-09-13 12:52:41Z

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

amit · Accepted Answer · 2012-09-13 23:12:19Z

0

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.

edited Sep 13, 2012 at 23:12

amit

179k27 gold badges245 silver badges348 bronze badges

answered Sep 13, 2012 at 11:26

Gloomcore

9507 silver badges11 bronze badges

Comments

Nazik · Accepted Answer · 2013-04-30 05:38:45Z

0

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

edited Apr 30, 2013 at 5:38

Nazik

8,45027 gold badges80 silver badges126 bronze badges

answered Apr 30, 2013 at 5:08

ravi

1

Collectives™ on Stack Overflow

Finding the missing number in an array

6 Answers 6

2 Comments

1 Comment

5 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

1 Comment

5 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related