## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
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
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
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. |

Powered by FogBugz