Determinar el número de desaparecidos en la secuencia de datos

Question

recibir una corriente de $ n-1 $ por pares diferentes números del conjunto $ \ left \ {1, \ dots, n \ right \} $.

¿Cómo puedo determinar el número que falta con un algoritmo que lee la corriente una vez y utiliza una memoria de sólo $ O (\ log_2 n) $ trozos?

Answer 1

Usted sabe que $ \ sum_ {i = 1} ^ ni = \ frac {n (n + 1)} {2} $, y debido $ S = \ frac {n (n + 1)} {2} $ podría ser codificado en $ O (\ log (n)) $ bits de esto se puede hacer en $ O (\ log n) $ memoria y en una ruta de acceso (acaba de encontrar $ S - \ mathrm {currentSum} $ número, esta falta ).

Sin embargo, este problema podría ser resuelto en el caso general (por constante k $ $): tenemos $ k $ números que faltan, descubrir todos ellos. En este caso, en lugar de calcular simplemente suma de $ $ y_i, suma del poder calcular j'st de $ x_i $ para todos $ 1 \ le j \ le k $ (asumí $ x_i $ es números que faltan y $ $ y_i es introducir números ):

$ \ qquad \ displaystyle \ begin {align} \ Sum_ {i = 1} ^ k = x_i y S_1, \\ \ Sum_ {i = 1} ^ k x_i ^ 2 & = S_2, \\ Y \ vdots \\ \ Sum_ {i = 1} ^ k x_i ^ k & = S_k \ End {align} $ $ \ qquad (1) $

Recuerde que se puede calcular $ S_1, ... $ S_k simplemente, porque S_1 $ = S - \ suma y_i $, $ S_2 = \ resumir i ^ 2 - \ suma y_i ^ 2 $, ...

Ahora, para encontrar los números que faltan se debe resolver $ (1) $ para encontrar todos los x_i $ $.

Puede calcular:

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

recuerde que $ P_1 = S_1 $, $ P_2 = \ frac {S_1 ^ 2 - S_2 } {2} $, ...

Pero P_i $ $ $ es coeficientes de P = (x-x 1) \ cdot (x-x_2) \ cdots (x-x_k) $, pero $ P $ podría tenerse en cuenta única, para que pueda encontrar los números que faltan.

Estos no son mis pensamientos; leer este .

Answer 2

A partir del comentario anterior:

Antes de procesar la corriente, asignar $ \ lceil \ log_2 n \ rceil $ bits, en el que se escriben $ x: = \ bigoplus_ {i = 1} ^ n \ mathrm {Bin} (i) $ ($ \ mathrm {bin} (i) $ es la representación binaria de $ i $ y $ \ oplus $ es puntual o-exclusiva). Ingenuamente, esto se lleva $ \ mathcal {O} (n) $ tiempo.

Después de procesar la corriente, cada vez que se lee un número $ j $, calcular $ x: = x \ oplus \ mathrm {bin} (j) $. Vamos $ k $ es el número único de $ \ {1, ... n \} $ que no está incluido en la corriente. Después de haber leído toda la corriente, tenemos $$ 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), $ PS produciendo el resultado deseado.

Por lo tanto, hemos utilizado $ \ mathcal {O} (\ log n) $ espacio, y tienen un tiempo de ejecución total de $ \ mathcal {O} (n) $.

Answer 3

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;
}