Zero out 2 locations in an array of size 10000, filled with integers from 1 to 10000. How do you find out what those values were? [duplicate]

Question

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

If you have an array of size 10000, filled with integers from 1 to 10000, no repeats, and you set two locations in that array to 0. How do you figure out what those two numbers were?

For example: Array = {8,6,3,5,4,2,7,1};//Array filled with numbers from 1 to 8 just for simplicity.

Array[0]=0; Array[1]=0;

What was in positions Array[0] and Array[1]?

If the question had only zero'd out one position the problem would be easy. You would take the sum of the numbers from 1 to 8 which is 36 and subtract it from the sum you get when you add up all the numbers in the array after a position was zero'd.

This is not a homework problem. But I think I remember being asked this question in college.

Answer 1

You can solve your problem with constant memory and 1 array lookup:

1. You can find the sum of zeroed numbers - by calculating the sum of all number minus sum of remaining ones
2. Similar way you can find the sum of the squares of zeroed numbers (only be careful to choose number types that can hold large enough values).

Now you have system of 2 equations with 2 variables (x+y==sum1 and x*x+y*y == sum2) that can easily be solved.