Find repeating in O(n) and constant space [duplicate]

Question

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.

Answer 1

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.

How to solve for x and y

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!