Missing Numbers II [Solution]

A solution to Missing Numbers II.

Stream of $n$ numbers: $1,2, \dots, n$, in some random order, and with two missing and two others repeated.

Need to given an $O(\log n)$ space and $O(n)$ time algorithm to find out the four numbers (repeated and missing).

Solution

---

As expected this uses Math.

Assume the numbers are $a,b,x,y$ the missing being $a,b$ and repeated being $x,y$.

Now in one pass we can compute the sum of $k^{th}$ powers of the numbers seen, and subtract from $1^k + 2^k + \dots + n^k$ to get

$$S_k =  a^k + b^k - x^k - y^k$$

We do this for $k=1,2,\dots 7$ (thus $O(\log n)$ space, and $O(n)$ time).

Now assume $a,b,x,y$ are roots of $P(z) = z^4 + pz^3 + qz^2 + rz + s$

This gives us the set of equations:

$$S_4 + pS_3 + q S_2 + rS_1 = 0$$
$$S_5 + pS_4 + q S_3 + rS_2  + sS_1 = 0$$
$$S_6 + pS_5 + q S_4 + rS_3 + sS_2= 0$$
$$S_7 + pS_6 + q S_5 + rS_4 + sS_3 = 0$$

Now the above set of equations is basically

$$P(a) + P(b) - P(x) - P(y) = 0$$
$$aP(a) + bP(b) - xP(x) - yP(y) = 0$$
$$a^2P(a) + b^2P(b) - x^2P(x) - y^2P(y) = 0$$
$$a^3P(a) + b^3P(b) - x^3P(x) - y^3P(y) = 0$$


Since the matrix

$$\begin{bmatrix}1&1&-1&-1\\a&b&-x&-y\\a^2&b^2&-x^2&-y^2\\a^3&b^3&-x^3&-y^3 \end{bmatrix}$$
 
is invertible (similar to a Vandermonde matrix) for distinct $a,b,x,y$, we have that $P(a) = P(b) = P(x) = P(y) = 0$.

Thus we solve for $p,q,r,s$ and find the roots of $P(z)$, either by verifying which of $1,2, \dots, n$ are roots, or by other means.