4

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.

Community
  • 1
  • 1
Jerinaw
  • 5,260
  • 7
  • 41
  • 54
  • Did you have any time bounds in mind? This problem is trivial to solve in O(n lg n) time or O(n) time with O(n) extra memory. – Fred Foo Jun 29 '11 at 19:31
  • @Jonderry Yes it is. Thanks, I tried searching before I posted, but was unable to find it. – Jerinaw Jun 30 '11 at 00:02

4 Answers4

4

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.

Vladimir
  • 170,431
  • 36
  • 387
  • 313
  • This works great thanks! It is what I was looking for. As @jonderry mentioned the solution is also found here http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-number – Jerinaw Jun 30 '11 at 14:46
2

I think this should work and is much more efficient than searching for every number:
-Sum all of the numbers
-Set two to 0
-Find the new sum
-Find all factors of the difference
-See which set of factors is possible based off of the numbers still in the array, since there are no repeats..

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;

Original Sum = 36
New Sum = 28
Difference = 8
Pairs that sum to 8: 7/1, 6/2, 5/3, 4/4
Check 6/2, see that 6 and 2 are both still there, rule out that pair. Continue until you find a pair that neither number is still in the array. That is your answer. In this case, neither 7 or 1 is still in the array, therefore that is the two numbers that were missing.

Andrew
  • 830
  • 3
  • 10
  • 27
  • Those are ([fortunately](https://secure.wikimedia.org/wikipedia/en/wiki/Integer_factorization)) not factors. – Fred Foo Jun 29 '11 at 19:37
  • Yea, I know.. I changed it in the bottom to Pairs but forgot to change it above. – Andrew Jun 30 '11 at 11:55
  • This will work too but I think it's less efficient than @Vladimir's. With this method you would have to search the array 4 times. With Vladimir's you would have to traverse it once to get the sums. You also have to determine all the pairs that add up to the difference. For a number like 5000 that might take a lot of work. – Jerinaw Jun 30 '11 at 14:57
  • I agree, I didn't think of his solution. Excellent. – Andrew Jun 30 '11 at 16:18
2

You could create a set with the numbers from 1 to 10000, walk through the array and remove from the set every number that you encounter in the array. At the end of the array your set should have the two numbers that were deleted.

Sai
  • 3,819
  • 1
  • 25
  • 28
1

You couldn't know what's the zeroed out numbers in the particular location of the array but you could know the 2 numbers by finding the missing nos. in your no. set.

acermate433s
  • 2,514
  • 4
  • 24
  • 32