algorithm - Find the missing and duplicate elements in an array in linear time and constant space

Question

You’re given an array of N 64 bit integers. N may be very large. You know that every integer 1..N appears once in the array, except there is one integer missing and one integer duplicated.

Write a linear time algorithm to find the missing and duplicated numbers. Further, your algorithm should run in small constant space and leave the array untouched.

Source: http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/

Answer 1

If all numbers were present in the array the sum would be N(N+1)/2.

Determine the actual sum by summing up all numbers in the array in O(n), let this be Sum(Actual).

One number is missing, let this be j and one number is duplicated, let this be k. That means that

Sum(Actual) = N(N+1)/2 + k - j

derived from that

k = Sum(Actual) -N(N+1)/2 + j

Also we can calculate the sum of squares in the array, which would sum up to n³/3 + n²/2 + n/6 if all numbers were present.

Now we can calculate the actual sum of squares in O(n), let this be Sum(Actual Squares).

Sum(Actual Squares) =n³/3 + n²/2 + n/6 + k² - j²

Now we have two equations with which we can determine j and k.