How to find two missing values in an array? [duplicate]

Question

This question already has answers here:

Closed 12 years ago.

Possible Duplicate:
Easy interview question got harder: given numbers 1..100, find the missing number(s)

A job interview question. Suppose we have an array of size N-2, with all the values from 1 to N, except for two missing values. (N>0)

An algorithm for finding the two missing numbers is needed, that traverses the array only once.

Answer 1

// Receiving array with values from 1 to N (NOT 0 to N-1)
// N is max value & # of values, NOT size of arr (arr is in size N-2)
void Find2Numbers(unsigned arr[], size_t N, unsigned & n1, unsigned & n2)
{
 unsigned sum = N*(N+1)/2; // sum of elements
 double pro = 1; // Products will be calculated within the loop, because fact(N) can be very large
 for(size_t i = 0 ; i < N-2 ; i++)
 {
 pro *= (i+1); // mult by i+1 to get factorial
 pro /= arr[i]; // divide by arr[i] to find n1*n2
 sum -= arr[i];
 }
 pro *= (N-1)*N; // 2 missing indexes, as arr is missing 2 elements
 // sum = n1+n2
 // pro = n1*n2 =>
 n1 = (sum+sqrt(sum*sum-4*pro))/2;
 n2 = (sum-sqrt(sum*sum-4*pro))/2;
}

• Leonid Volnitsky: @NPE - you multiply and then you immediately divide.
• StackHeapCollision: @NPE - I've ran it for N=10,000 and it works just fine. I would have checked it for 100,000 but sum=N*(N+1) overflows, so you can take the code and change it to calculate sum within the loop as well to see if works for a very large N.
• NPE: @LeonidVolnitsky: Oh, I missed the division. Question withdrawn.