1
$\begingroup$

I saw this post and wondered why the approach described in the accepted answer works. The same problem and solution is described a bit nicer here.

So let's say we receive a stream of $n-2$ pairwise different numbers $a_1 + a_2 + \cdots + a_{n-2}$, from the set $\left\{1,\dots,n\right\}$. What I learned from the above post is that for the problem of finding 2 missing numbers $x$ and $y$, given a stream as described above, can be solved by finding the solution to the following system of equations:

\begin{alignat*}{4} x+y & {}={} & \dfrac{n(n+1)}{2} - (a_1 + a_2 + \cdots + a_{n-2}) \\ x^2 + y^2 & {}={} & \dfrac{n(n+1)(2n+1)}{6} - (a_1^2 + a_2^2 + \cdots + a_{n-2}^2) \end{alignat*}

Now it is easy to convert this into a single pass algorithm which supposedly returns the two missing numbers for a given stream.

How would one prove this algorithm's correctness? I think showing that the system must have exactly two solutions would be enough to prove correctness but I'm not sure how to approach this?

How can I convince myself (and others) that the algorithm is correct?

$\endgroup$
1
$\begingroup$

Suppose that $x + y = A$ and $x^2 + y^2 = B$. Then $$ xy = \frac{(x+y)^2 - (x^2+y^2)}{2} = \frac{A^2-B}{2}. $$ Consider now the polynomial $$ (t-x)(t-y) = t^2 - (x+y)t + xy = t^2-At + \frac{A^2-B}{2}. $$ The polynomial on the right has the two roots $x,y$.

If $x + y = z + w$ and $x^2 + y^2 = z^2 + w^2$ then both $x,y$ and $z,w$ are the two roots of the same polynomial, and so $\{x,y\} = \{z,w\}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.