Bestimmen Sie die fehlende Nummer im Datenstrom

Question

Wir erhalten einen Stream von $ n-1 $ paarweise verschiedene Zahlen von der festgelegten $ links {1, dots, n right } $.

Wie kann ich die fehlende Zahl mit einem Algorithmus bestimmen, der den Stream einmal liest und einen Speicher von nur $ O ( log_2 n) $ Bits verwendet?

Answer 1

Sie wissen In $ o ( log (n)) $ Bits kann dies in $ o ( log n) $ Memory und in einem Pfad erfolgen (nur $ s - mathrm {currentsum} $ finden, fehlt diese Nummer).

Dieses Problem könnte jedoch im allgemeinen Fall gelöst werden (für konstante $ k $): Wir haben fehlende Zahlen von $ k $, finden Sie alle heraus. In diesem Fall berechnen Sie die Summe von J'St Power von $ x_i $ für alle $ 1 le j le k $ (ich nahm an, $ x_i $ fehlt die Nummern und $ y_i $ ist die Eingabeberechnen, anstatt nur Summe von $ y_i $ zu berechnen, anstatt zu berechnen. ):

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

Denken Sie daran, dass Sie $ s_1, ... s_k $ einfach berechnen können, weil $ s_1 = s - sum y_i $, $ s_2 = sum i^2 - sum y_i^2 $, ...

Um fehlende Zahlen zu finden, sollten Sie $ (1) $ lösen, um alle $ x_i $ zu finden.

Sie können berechnen:

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

Dafür erinnere dich daran $ P_1 = s_1 $, $ p_2 = frac {s_1^2 - s_2} {2} $, ...

Aber $ p_i $ sind Koeffizienten von $ p = (x-x_1) cdot (x-x_2) cdots (x-x_k) $ aber $ p $ könnte berücksichtigt werden Eindeutig, damit Sie fehlende Zahlen finden können.

Das sind nicht meine Gedanken; lesen Dies.

Answer 2

Aus dem obigen Kommentar:

Bevor Sie den Stream verarbeiten, geben Sie $ lceil log_2 n rceil $ bits, in dem Sie $ x: = bigoplus_ {i = 1}^n mathMathrm {bin} (i) $ ($ mathrm {bin} schreiben (i) $ ist die binäre Vertretung von $ i $ und $ oplus $ is pointiell exklusiv-or). Naiv ist dies $ mathcal {o} (n) $ time.

Berechnen Sie bei der Verarbeitung des Streams $ x: = x oPlus mathrm {bin} (j) $, wenn man eine Nummer $ J $ liest. Sei $ k $ die einzelne Nummer von $ {1, ... n } $, die nicht im Stream enthalten ist. Nach dem Lesen des gesamten Stream mathhrm {bin} (i) right) = mathrm {bin} (k) oplus bigoplus_ {i neq k} ( mathhrm {bin} (i) oplus mathrm {bin} (i)) = mathrm {bin} (k), $$, das das gewünschte Ergebnis ergibt.

Daher haben wir $ mathcal {o} ( log n) $ space verwendet und haben eine Gesamtlaufzeit von $ mathcal {o} (n) $.

Answer 3

Die Lösung von HDM funktioniert. Ich habe es in C ++ codiert, um es zu testen. Ich kann das nicht einschränken value bis $ o ( log_2 n) $ bit, aber ich bin sicher, Sie können leicht zeigen, wie nur diese Anzahl der Bits tatsächlich festgelegt ist.

Für diejenigen, die Pseudo -Code wünschen, verwenden Sie einen einfachen $ text {fold} $ operation mit exklusivem oder ($ oplus $):

$$ text {fehlend} = text {fold} ( oplus, {1, ldots, n } cup text {inputStream}) $$

Handwelliger Beweis: Ein $ oplus $ erfordert nie mehr Bits als seine Eingabe. Daher folgt, dass kein Zwischenergebnis in das oben genannte mehr als die maximalen Bits der Eingabe (also $ o ( log_2 n) $ Bits) erforderlich ist. $ oPlus $ ist kommutativ und $ x oplus x = 0 $. Wenn Sie also das oben genannte erweitern und alle im Stream vorhandenen Daten abbilden, werden Sie nur mit einem einzelnen nicht angestimmten Wert, der fehlenden Zahl, belassen.

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