Extract 2 places in an array of size 10,000, filled with integers from 1 to 10,000. How do you know what these values ​​are?

Question

Possible duplicate:
The question of a simple interview is complicated: considering the numbers 1..100, find the missing numbers

If you have an array of size 10000 filled with integers from 1 to 10000, there are no repetitions, and you set two locations in this array to 0. How did you find out what these two numbers are?

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

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

What were the positions of Array [0] and Array [1]?

If the question left only one zero position, the problem would be easy. You would take the sum of numbers from 1 to 8, which is 36, and subtract it from the amount you get when you sum all the numbers in the array after the position was zero.

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

Answer 1

You can solve your problem with read-only memory and one array search:

• You can find the sum of zero numbers - by calculating the sum of the whole number minus the sum of the remaining
• Similarly, you can find the sum of the squares of zeros (be careful to choose the types of numbers that can contain large enough values).

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

Answer 2

I think this should work and be much more efficient than finding each number:
-Totaling all numbers
-Set two to 0
-Write a new amount
-See all the difference factors
-Specify which set of factors is possible, based on the numbers still in the array, since there are no repetitions.

For instance:
Array = {8,6,3,5,4,2,7,7}; // The array is filled with numbers from 1 to 8 just for simplicity.
Array [0] = 0;
Array [1] = 0;

Original amount = 36
New Amount = 28
Difference = 8
Pairs that add up to 8: 7/1, 6/2, 5/3, 4/4
Check 6/2, see that 6 and 2 are still there, exclude this pair. Continue until you find a pair in which no number is in the array. This is your answer. In this case, neither 7 nor 1 is still in the array, so these are two numbers that were missing.

Answer 3

You can create a set with numbers from 1 to 10000, go through the array and remove from the set all the numbers that you encounter in the array. At the end of the array, your set should have two numbers that have been removed.

Answer 4

You could not know what zero digits in a certain place of the array, but you could find out 2 numbers by finding the missing numbers. in your not. set.