Fastest way to find 2 missing numbers in an array

Question

This question exist only because of pure curiosity. Not a homework.

Find the fastest way to find two missing number in an array 1..n

So, In a related post: Quickest way to find missing number in an array of numbers I found out that you can do this pretty quickly by summing up and substracting total.

but what about 2 numbers?

So, our options are:

1. Sequential search
2. Summing up items, substracting from total for all items from 1..n, then searching all possible cases.

Anything else? Possible to have O(n) solution? I found this in ruby section of one of the websites, but any language is considered (unless there are some specific things for a language)

Answer 1

1. Find the sum of the numbers S=a1+...+an.
2. Also find the sum of squares T=a1*a1+...+an*an.
3. You know that the sum should be S'=1+...+n=n(n+1)/2
4. You know that the sum of squares should be T'=1^2+...+n^2=n(n+1)(2n+1)/6.
5. Now set up the following system of equations x+y=S'-S, x^2+y^2=T'-T.
6. Solve by writing x^2+y^2=(x+y)^2-2xy => xy=((S'-S)^2-(T'-T))/2. And now the numbers are merely the roots of the quadratic in z: z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0.

Answer 2

The simple way (and pretty fast too:)

a = [1,2,3,5,7]
b = (1..7).to_a
p b-a #=> [4, 6]