RSS Feed

techInterview Discussion

You have an array of size 100 which stores integers from 0 to 99.
In this array one number is a duplicate, that means one is missing.

How can we find duplicate and missing ?

My approach -

Sort the array by insertion sort (since it is already mostly sorted, we can do it in almost order N). Once that is done we can compare adjacent numbers to find our duplicate. How can we find missing by this approach ?

Another shot - since we know this is an array from 0 to 99 we only need to walk the array comparing the index in the array with the value at that index, if there is no match we know our duplicate and also missing.

We could also use mathematical apprach by making 2 equations for summations and products....

Any other better ways to do this ?

thanks.

Nit: We do not know that the array is mostly sorted.  You added that after the problem statement.  Note that it is irrelevant for my algorithm.

This algorithm is brittle.  Should the array of numbers not be as stated, the results will be nonsense.

Number[] is the array of numbers.  DupValue is the duplicate value.  MissingValue is the omitted value.

boolean Met[0..99] init all false
int Sum=0
for int i=0 to 99
  Sum+=Number[i]
  if Met[Number[i]]
  DupValue=Number[i]
  else
    Met[Number[i]]=true
int Diff=4950-Sum  // Sum of 0..99=4950
MissingValue=DupValue+Diff

Sincerely,

Gene Wirchenko

@hmmm

You can do this in O(n) is without using any extra space.

Instead of using two equations for sums and products (99! is a *very* big number), you can use sums and 'sums of sqaures' instead:

1 + 2 + 3 + 4 + 5 + ... + 99 = 4950

1 + 4 + 9 + 16 + 25 + ... +  9801 = 328350

Here's some pseudocode:

s1 = 0;
s2 = 0;

for (i = 0; i <= 99; i++) {
  s1 += n[i];
  s2 += n[i]*n[i];
}

d1 = 4950 - s1;
d2 = 328350 - s2;

m = (d1 + d2/d1)/2;
d = m - d1;

m is the missing number, and d is the duplicate.

i think m is the duplicate & d is the  missing no.
correct me if  i am wrong

one more approach :
traverse the array and value the j=a[i] with a[j], untill u get collision which i steh  reapeated no. .
but do this for all the array.


now again traverse the array and find out the locations of the duplicate no. , one location is the correct position, which is equal to the no. whereas other i s the position f the missing no.

It is really much simpler than all this.

O(n)

Find sum of all the elements in the array. And compare it with sum of 0 to 99, to find the missing number.