Consider this problem: A list of distinctive integers in random order is provided. The integer is in the range of to and there are integers provided, i.e. one integer in is not in the provided list. Find that number in space and time.
Simply, we sum up the numbers in the list and the difference between the sum and is the number in concern.
But what happen if there are two numbers missing? Obviously, we can use the same trick, for the list of integers be denoted by , we find
Then we have the two missing numbers, and , to satisfy
This approach works but can be a vastly large number. Can we have another simultaneous equations to find and without overflowing an integer variable?
I have considered the following
and some others. However, I find one test to prove if any of these constructs can help you solve the two unknowns. Consider and are different at bit , and we define and to be same as and except their bit are flipped. Then we should have a function that
or otherwise we cannot distinguish the solution , from , . Obviously the list above does not pass this test. That’s why we need multiplication involved: We can solve for and in the equations below
It can also be done using a non-linear injective function other than square in the second equation, such as logarithms. However, logarithm produce floating point numbers and that may introduce noise. This is not a good solution in implementation perspective because, increases quicker than linear and it has a chance to overflow the variable. But this is the best solution I get so far.