techInterview Discussion

Answers to technical interview questions. A part of TechInterview.org

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Duplicate and missing

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.
hmmm
Wednesday, December 31, 2008
 
 
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
Gene Wirchenko Send private email
Wednesday, December 31, 2008
 
 
@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
Sajid
Tuesday, February 03, 2009
 
 
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.
Sajid
Wednesday, February 04, 2009
 
 
i think m is the duplicate & d is the  missing no.
correct me if  i am wrong
guruji Send private email
Saturday, February 21, 2009
 
 
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.
guruji Send private email
Saturday, February 21, 2009
 
 
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.
Sunjeet Send private email
Sunday, February 22, 2009
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz