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: Sequential search 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) JavaScript questions and answers, JavaScript questions pdf, JavaScript question bank, JavaScript questions and answers pdf, mcq on JavaScript pdf, JavaScript questions and solutions, JavaScript mcq Test , Interview JavaScript questions, JavaScript Questions for Interview, JavaScript MCQ (Multiple Choice Questions)

Answer 1

Find the sum of the numbers S=a1+...+an. Also find the sum of squares T=a1*a1+...+an*an. You know that the sum should be S'=1+...+n=n(n+1)/2 You know that the sum of squares should be T'=1^2+...+n^2=n(n+1)(2n+1)/6. Now set up the following system of equations x+y=S'-S, x^2+y^2=T'-T. 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.