Find two missing numbers

Question

We have a machine with O(1) memory and we want to pass n numbers (one by one) in the first pass, and then we exclude the two numbers and we will pass n-2 numbers to the machine.

write an algorithm that finds missing numbers.

Answer 1

It can be done with O(1) memory.

You only need a few integers to keep track of some running sums. The integers do not require log n bits (where n is the number of input integers), they only require 2b+1 bits, where b is the number of bits in an individual input integer.

When you first read the stream add all the numbers and all of their squares, i.e. for each input number, n, do the following:

sum += n
sq_sum += n*n

Then on the second stream do the same thing for two different values, sum2 and sq_sum2. Now do the following maths:

sum - sum2 = a + b
sq_sum - sq_sum2 = a^2 + b^2

(a + b)(a + b) = a^2 + b^2 + 2ab
(a + b)(a + b) - (a^2 + b^2) = 2ab
(sum*sum - sq_sum) = 2ab

(a - b)(a - b) = a^2 + b^2 - 2ab
               = sq_sum - (sum*sum - sq_sum) = 2sq_sum - sum*sum
sqrt(2sq_sum - sum*sum) = sqrt((a - b)(a - b)) = a - b
((a + b) - (a - b)) / 2 = b
(a + b) - b = a

You need 2b+1 bits in all intermediate results because you are storing products of two input integers, and in one case multiplying one of those values by two.

Answer 2

The following came to my mind as soon as I finished reading the question. But the answers above suggest that it is not possible with O(1) memory or that there should be a constraint on the range of numbers. Tell me if my understanding of the question is wrong. Ok, so here goes

You have O(1) memory - which means you have constant amount of memory.

When the n numbers are passed to you 1st time, just keep adding them in one variable and keep multiplying them in another. So at the end of 1st pass you have the sum and product of all the numbers in 2 variables S1 and P1. You have used 2 variable till now (+1 if you reading the numbers in memory).

When the (n-2) numbers are passed to you the second time, do the same. Store the sum and product of the (n-2) numbers in 2 other variables S2 and P2. You have used 4 variables till now (+1 if you reading the numbers in memory).

If the two missing numbers are x and y, then

x + y = S1 - S2
x*y = P1/P2;

You have two equations in two variables. Solve them.

So you have used a constant amount of memory (independent of n).

Answer 3

Assuming the numbers are ranging from 1..N and 2 of them are missing - x and y, you can do the following:

Use Gauss formula: sum = N(N+1)/2

sum - actual_sum = x + y

Use product of numbers: product = 1*2..*N = N!

product - actual_product = x * y

Resolve x,y and you have your missing numbers.

In short - go through the array and sum up each element to get the actual_sum, multiply each element to get actual_product. Then resolve the two equations for x an y.