Hackermeter's Double Duplicates challenge

There is a coding challenge at hackermeter.

We are given a serie of \(X+2\) integers that contains all integers from \(1\) to \(X\), plus two integers in \(\left[\!\left[{1..X}\right]\!\right]\). The goal is to find these two duplicated integers, using as little memory as possible.

Edit : rules have changed at hackermeter.com ! Now, the serie takes its integers in the interval \(\left[\!\left[{0..X-1}\right]\!\right]\). That doesn't modify the algorithm below, but care must be taken at implementation time.

A trivial solution could use a \(X\)-bits bitmap, but this requires about \(X/8\) bytes of memory.

Here is a solution that is an \(O(1)\) with respect to memory (ie, needed memory doesn't depends on \(n\)).

The trick is to maintain two sums along the stream of read integers: the sum of the integers (\(\Sigma_1\)), and the sum of the square of these integers (\(\Sigma_2\)).

Here it is :

Let \(\Sigma_1\) be the sum of integers from \(1\) to \(X\) and \(\Sigma_2\) be the sum of the square of integers from \(1\) to \(X\) : $$ \left\{ \begin{matrix} \Sigma_1&=&\sum_{n=1}^{X}n & = & {X(X+1) \over 2} \\ \\ \Sigma_2&=&\sum_{n=1}^{X}n^2 & = & {X(X+1)(2X+1) \over 6} \end{matrix} \right. $$ Let \(\alpha_n\) be the \(n\)-th term of the given serie. We can compute \(\sigma_1\) and \(\sigma_2\) defined by: $$ \left\{ \begin{matrix} \sigma_1 & = & \sum_{n=1}^{X+2}\alpha_n \\ \\ \sigma_2 & = & \sum_{n=1}^{X+2}{\alpha_n}^2 \end{matrix} \right. $$ With \(\delta_1\) and \(\delta_2\) the two integers that are duplicated. We have : $$ \left\{ \begin{matrix} \sigma_1 - \Sigma_1 & = & \delta_1 + \delta_2 \\ \\ \sigma_2 - \Sigma_2 & = & \delta_1^2 + \delta_2^2 \end{matrix} \right. $$ That gives : $$ \left\{ \begin{matrix} \sigma_1 - \Sigma_1 = \delta_1 + \delta_2 \\ \\ 2\delta_2^2 + 2(\Sigma_1-\sigma_1)\delta_2+(\sigma_1-\Sigma_1)^2+\Sigma_2-\sigma_2 = 0 \end{matrix} \right. $$ Then, with \(\Delta = 4(\Sigma_1-\sigma_1)^2 - 8((\sigma_1-\Sigma_1)^2+\Sigma_2-\sigma_2)\) : $$ \left\{ \begin{matrix} \delta_1 = {-2(\Sigma_1-\sigma_1) -\sqrt{\Delta} \over 4} \\ \delta_2 = {-2(\Sigma_1-\sigma_1) +\sqrt{\Delta} \over 4} \end{matrix} \right. $$ (\(\delta_1\) and \(\delta_2\) are permutable, yes)

I leave you implementing this in the language of your choice, as an exercise ;)