Find two missing numbers

It cannot be done with O(1) memory.

Assume you have a constant k bits of memory - then you can have 2^k possible states for your algorithm.

However - input is not limited, and assume there are (2^k) + 1 possible answers for (2^k) + 1 different problem cases, from piegeonhole principle, you will return the same answer twice for 2 problems with different answers, and thus your algorithm is wrong.

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.

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.