14
$\begingroup$

We receive a stream of $n-1$ pairwise different numbers from the set $\left\{1,\dots,n\right\}$.

How can I determine the missing number with an algorithm that reads the stream once and uses a memory of only $O(\log_2 n)$ bits?

$\endgroup$
7
$\begingroup$

You know $\sum_{i=1}^n i = \frac{n(n+1)}{2}$, and because $S = \frac{n(n+1)}{2}$ could be coded in $O(\log(n))$ bits this can be done in $O(\log n)$ memory and in one path (just find $S - \mathrm{currentSum}$, this is missing number).

But this problem could be solved in general case (for constant $k$): we have $k$ missing numbers, find out all of them. In this case instead of calculating just sum of $y_i$, calculate sum of j'st power of $x_i$ for all $1\le j \le k$ (I assumed $x_i$ is missing numbers and $y_i$ is input numbers):

$\qquad \displaystyle \begin{align} \sum_{i=1}^k x_i &= S_1,\\ \sum_{i=1}^k x_i^2 &= S_2,\\ &\vdots \\ \sum_{i=1}^k x_i^k &= S_k \end{align}$ $\qquad (1)$

Remember that you can calculate $S_1,...S_k$ simply, because $S_1 = S - \sum y_i$, $S_2 = \sum i^2 - \sum y_i^2$, ...

Now for finding missing numbers you should solve $(1)$ to find all $x_i$.

You can compute:

$P_1 = \sum x_i$, $P_2 = \sum x_i\cdot x_j$, ... , $P_k = \prod x_i$ $(2)$.

For this remember that $P_1 = S_1$, $P_2 = \frac{S_1^2 - S_2}{2}$, ...

But $P_i$ is coefficients of $P=(x-x_1)\cdot (x-x_2) \cdots (x-x_k)$ but $P$ could be factored uniquely, so you can find missing numbers.

These are not my thoughts; read this.

$\endgroup$
  • 1
    $\begingroup$ I don't get (2). Maybe if you added in the sums' details? Does $P_k$ miss a $\sum$? $\endgroup$ – Raphael May 26 '12 at 12:43
  • $\begingroup$ @Raphael, $P_i$ is Newton's identities, I think if you take a look at my referenced wiki page you can get the idea of calculation, each $P_i$ could be calculated by previous $P$s, $S_j$, remember simple formula: $2 \cdot x_1 \cdot x_2 = (x_1 + x_2)^2 - (x_1^2 + x_2^2)$, you can apply similar approach to all powers. Also as I wrote $P_i$ is sigma of something, but $P_k$ doesn't have any $\Sigma$, because there is just one $\Pi$. $\endgroup$ – user742 May 26 '12 at 13:24
  • $\begingroup$ Be that as it may, answers should be self-contained to a reasonable degree. You give some formulae, so why not make them complete? $\endgroup$ – Raphael May 26 '12 at 14:35
11
$\begingroup$

From the comment above:

Before processing the stream, allocate $\lceil \log_2 n \rceil$ bits, in which you write $x:= \bigoplus_{i=1}^n \mathrm{bin}(i)$ ($\mathrm{bin}(i)$ is the binary representation of $i$ and $\oplus$ is pointwise exclusive-or). Naively, this takes $\mathcal{O}(n)$ time.

Upon processing the stream, whenever one reads a number $j$, compute $x := x \oplus \mathrm{bin}(j)$. Let $k$ be the single number from $\{ 1, ... n\}$ that is not included in the stream. After having read the whole stream, we have $$ x = \left(\bigoplus_{i=1}^n \mathrm{bin}(i)\right) \oplus \left(\bigoplus_{i \neq k } \mathrm{bin}(i)\right) = \mathrm{bin}(k) \oplus \bigoplus_{i \neq k } (\mathrm{bin}(i) \oplus \mathrm{bin}(i)) = \mathrm{bin}(k), $$ yielding the desired result.

Hence, we used $\mathcal{O}(\log n)$ space, and have an overall runtime of $\mathcal{O}(n)$.

$\endgroup$
  • 3
    $\begingroup$ may I suggest an easy optimization that makes this a true streaming single-pass algorithm: at time step $i$, xor $x$ with $\mathrm{bin}(i)$ and with the input $\mathrm{bin}(j)$ that has arrived on the stream. this has the added benefit that you can make it work even if $n$ is not known ahead of time: just start with a single bit allocated for $x$ and "grow" the allocated space as necessary. $\endgroup$ – Sasho Nikolov May 28 '12 at 4:34
0
$\begingroup$

HdM's solution works. I coded it in C++ to test it. I can't limit the value to $O(\log_2 n)$ bits, but I'm sure you can easily show how only that number of bits is actually set.

For those that want pseudo code, using a simple $\text{fold}$ operation with exclusive or ($\oplus$):

$$\text{Missing} = \text{fold}(\oplus, \{1,\ldots,N\} \cup \text{InputStream})$$

Hand-wavey proof: A $\oplus$ never requires more bits than its input, so it follows that no intermediate result in the above requires more than the maximum bits of the input (so $O(\log_2 n)$ bits). $\oplus$ is commutative, and $x \oplus x = 0$, thus if you expand the above and pair off all data present in the stream you'll be left only with a single un-matched value, the missing number.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

void find_missing( int const * stream, int len );

int main( int argc, char ** argv )
{
    if( argc < 2 )
    {
        cerr << "Syntax: " << argv[0] << " N" << endl;
        return 1;
    }
    int n = atoi( argv[1] );

    //construct sequence
    vector<int> seq;
    for( int i=1; i <= n; ++i )
        seq.push_back( i );

    //remove a number and remember it
    srand( unsigned(time(0)) );
    int remove = (rand() % n) + 1;
    seq.erase( seq.begin() + (remove - 1) );
    cout << "Removed: " << remove << endl;

    //give the stream a random order
    std::random_shuffle( seq.begin(), seq.end() );

    find_missing( &seq[0], int(seq.size()) );
}

//HdM's solution
void find_missing( int const * stream, int len )
{
    //create initial value of n sequence xor'ed (n == len+1)
    int value = 0;
    for( int i=0; i < (len+1); ++i )
        value = value ^ (i+1);

    //xor all items in stream
    for( int i=0; i < len; ++i, ++stream )
        value = value ^ *stream;

    //what's left is the missing number
    cout << "Found: " << value << endl;
}
$\endgroup$
  • 3
    $\begingroup$ Please post readable (pseudo) code of only the algorithm instead (skip main). Also, a correctness proof/argument at some level should be included. $\endgroup$ – Raphael May 26 '12 at 9:26
  • 4
    $\begingroup$ @edA-qamort-ora-y Your answer assumes that the reader knows C++. To someone who is not familiar with this language, there is nothing to see: both finding the relevant passage and understanding what it's doing are a challenge. Readable pseudocode would make this a better answer. The C++ is not really useful on a computer science site. $\endgroup$ – Gilles May 26 '12 at 10:22
  • 3
    $\begingroup$ If my answer proves not to be useful people don't need to vote for it. $\endgroup$ – edA-qa mort-ora-y May 26 '12 at 10:37
  • 2
    $\begingroup$ +1 for actually taking the time to write C++ code and test it out. Unfortunately as others pointed out, it's not SO. Still you put effort into this ! $\endgroup$ – Julien Lebot May 26 '12 at 11:59
  • 9
    $\begingroup$ I don't get the point of this answer: you take someone else's solution, which is very simple and obviously very efficient, and "test" it. Why is testing necessary? This is like testing your computer adds numbers correctly. And there is nothing nontrivial abt your code either. $\endgroup$ – Sasho Nikolov May 27 '12 at 13:30

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.