Determinare numero mancante nel flusso di dati

Question

ricevere un flusso di $ n-1 numeri $ a coppie diverse dal set $ \ left \ {1, \ dots, n \ right \} $.

Come è possibile determinare il numero mancante con un algoritmo che legge il flusso di una volta e utilizza una memoria di soli $ O (\ log_2 n) $ bit?

Answer 1

Sai $ \ sum_ {i = 1} ^ ni = \ frac {n (n + 1)} {2} $, e per $ S = \ frac {n (n + 1)} {2} $ potrebbe essere codificato in $ O (\ log (n)) $ bit questo può essere fatto in $ O (\ log n) $ memoria e in un percorso (solo trovare $ S - \ mathrm {currentSum} numero di $, questo manca ).

Ma questo problema potrebbe essere risolto nel caso generale (per il costante $ k $): abbiamo $ k numeri $ mancanti, scoprire tutti loro. In questo caso, invece di calcolare solo somma di $ $ y_i, somma Calcolare del potere j'st di $ x_i $ per tutti i $ 1 \ le j \ le k $ (ho assunto $ x_i $ manca numeri e $ y_i $ è immettere i numeri ):

$ \ 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) $

Si ricorda che è possibile calcolare $ S_1, ... S_k $ semplicemente, perché $ S_1 = S - \ somma y_i $, $ S_2 = \ sum I ^ 2 - \ somma y_i ^ 2 $, ...

Ora, per trovare i numeri mancanti si dovrebbe risolvere $ (1) $ trovare tutte $ x_i $.

È possibile calcolare:

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

Per questo ricordare che $ P_1 = S_1 $, $ P_2 = \ frac {S_1 ^ 2 - S_2 } {2} $, ...

Ma $ p_i $ è coefficienti di $ P = (x-x_1) \ cdot (x-x_2) \ cdots (x-x_k) $ ma $ P $ potrebbero essere presi unico, in modo da poter trovare i numeri mancanti.

Questi non sono i miei pensieri; leggere questo .

Answer 2

Dal commento di cui sopra:

Prima di elaborare il flusso, allocare $ \ lceil \ log_2 n \ rceil $ bit, in cui si scrive $ x: = \ bigoplus_ {i = 1} ^ n \ mathrm {bin} (i) $ ($ \ mathrm {bin} (i) $ è la rappresentazione binaria di $ i $ e $ \ oplus $ è puntuale esclusiva-o). Ingenuamente, questo richiede $ \ mathcal {} O (n) $ tempo.

Una volta elaborati i torrente, ogni volta che si legge un numero $ j $, calcolare $ x: = x \ oplus \ mathrm {bin} (j) $. Diamo $ k $ essere il numero unico da $ \ {1, ... n \} $ che non è incluso nel flusso. Dopo aver letto l'intero flusso, abbiamo $$ 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), $ $ ottiene il risultato desiderato.

Quindi, abbiamo usato $ \ mathcal {O} (\ log n) $ spazio, e hanno un tempo di esecuzione complessivo di $ \ mathcal {} O (n) $.

Answer 3

La soluzione di HdM funziona. Ho codificato in C ++ per testarlo. Non riesco a limitare la value a $ O (\ log_2 n) $ bit, ma sono sicuro che si può facilmente mostrare come solo quel numero di bit è effettivamente impostato.

Per coloro che vogliono pseudo codice, utilizzando un semplice $ \ text {} piegare $ operazione con esclusivo o ($ \ oplus $):

$$ \ text {mancante} = \ text {} volte (\ oplus, \ {1, \ ldots, N \} \ tazza \ text {} InputStream) $$

a mano Mossi prova: A $ \ oplus $ non richiede mai più bit rispetto al suo ingresso, quindi ne consegue che nessun risultato intermedio in quanto sopra richiede più di bit massima dell'ingresso (modo $ O (\ log_2 n) $ bit). $ \ Oplus $ è commutativa, e $ x \ oplus x = 0 $, quindi se si espande quanto sopra e coppia di fuori di tutti i dati presenti nel flusso ti verrà lasciato solo con un singolo valore non-abbinato, il numero mancante.

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