Menu
Possible Duplicate:
Easy interview question got harder: given numbers 1..100, find the missing number(s)
Find the missing and duplicate elements in an array in linear time and constant space
I saw an interesting Question on one forum.
you have 100 elements from 1 to 100 but byy mistake one of those number overlapped another by repeating itself. E.g. 1,99,3,...,99,100 Array is not in sorted format , how to find the repeating number ?
I know Hash can do it O(n) time and O(n) space, I need O(1) space.
913
Naive approach: Use 2 loops. Check each element in the array with all other elements in the array and check if it has the same value. Sorting approach: Sort the array, this will bring all the duplicates together if present. Now navigate the array and check the adjacent elements to check for duplicates.
Calculate two sums: sum and square sum.
In your example:
sum = 1+99+3...+100
sq_sum = 1^2+99^2+3^2+...+100^2
Assume y replaced x in the sequence.
sum = n(n+1)/2 -y+x.
sq_sum = n(n+1)(2n+1)/6 -x^2 +y^2
Now, solve for x & y.
Constant space and O(n) time.
From equation:
x = sum - n(n+1)/2 +y
Substitute this in the second equation:
sq_sum = n(n+1)(2n+1)/6 -(sum - n(n+1)/2 +y)^2 +y^2
Note that y^2 cancels and you are left with a linear equation with only one unknown:y. Solve it!
52
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
