Tentukan nomor yang hilang dalam aliran data

Kami menerima aliran $n-1$ angka yang berbeda secara berpasangan dari set $\left\{1,\dots,n\right\}$ .

Bagaimana saya bisa menentukan angka yang hilang dengan algoritma yang membaca aliran sekali dan menggunakan memori hanya $O(\log_2 n)$ bit?

Anda tahu , dan karenaS=n(n+1$\sum_{i=1}^n i = \frac{n(n+1)}{2}$ dapat dikodekan dalambitO(log(n))ini dapat dilakukan dalammemoriO(logn)dan dalam satu jalur (cukup cariS-currentSum, ini adalah nomor yang hilang).$S = \frac{n(n+1)}{2}$$O(\log(n))$$O(\log n)$$S - \mathrm{currentSum}$

Tetapi masalah ini dapat diselesaikan dalam kasus umum (untuk konstan ): kami memiliki nomor k yang hilang, cari tahu semuanya. Dalam hal ini, alih-alih menghitung hanya jumlah y i , hitung jumlah kekuatan pertama x i untuk semua 1 ≤ j ≤ k (saya berasumsi x i adalah angka yang hilang dan y i adalah angka input):$k$$k$$y_i$$x_i$$1\le j \le k$$x_i$$y_i$

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

Ingat bahwa Anda dapat menghitung sederhana, karena S 1 = S - Σ y i , S 2 = Σ i 2 - Σ y $S_1,...S_k$$S_1 = S - \sum y_i$ , ...$S_2 = \sum i^2 - \sum y_i^2$

Sekarang untuk menemukan nomor yang hilang, Anda harus memecahkan $(1)$ untuk menemukan semua .$x_i$

Anda dapat menghitung:

, P 2 = ∑ x i ⋅ x j , ..., P k = ∏ x i ( 2 ) .$P_1 = \sum x_i$$P_2 = \sum x_i\cdot x_j$$P_k = \prod x_i$ $(2)$

Untuk ini ingat bahwa , P 2 = S 2 1 - S $P_1 = S_1$ , ...$P_2 = \frac{S_1^2 - S_2}{2}$

Tetapi adalah koefisien dari $P_i$$P=(x-x_1)\cdot (x-x_2) \cdots (x-x_k)$ tetapi dapat diperhitungkan secara unik, sehingga Anda dapat menemukan angka yang hilang.$P$

Ini bukan pikiran saya; Baca ini .

Dari komentar di atas:

Sebelum memproses aliran, alokasikan bit, di mana Anda menulis x : = ⨁ n i = 1 b i n ( i ) ( b i n ( $\lceil \log_2 n \rceil$$x:= \bigoplus_{i=1}^n \mathrm{bin}(i)$ adalah representasi biner dari i dan ⊕ adalah pointwise eksklusif- atau). Secara naif, ini membutuhkan waktu O ( n ) .$\mathrm{bin}(i)$$i$$\oplus$$\mathcal{O}(n)$

Setelah memproses streaming, setiap kali seseorang membaca angka , hitung x : = x ⊕ b i n ( j ) . Biarkan k menjadi nomor tunggal dari { 1 , . . . n } yang tidak termasuk dalam aliran. Setelah membaca seluruh aliran, kita memiliki x = ( n ⨁ i = 1 b i n ( i ) ) ⊕ ( ⨁ i ≠ k$j$$x := x \oplus \mathrm{bin}(j)$$k$$\{ 1, ... n\}$

$\mathcal{O}(\log n)$$\mathcal{O}(n)$

Solusi HdM bekerja. Saya mengkodekannya dalam C ++ untuk mengujinya. Saya tidak bisa membatasi valueuntuk$O(\log_2 n)$ bit, tapi saya yakin Anda dapat dengan mudah menunjukkan bagaimana hanya jumlah bit yang benar-benar ditetapkan.

Bagi yang menginginkan kode pseudo, gunakan yang sederhana $\text{fold}$ operasi dengan eksklusif atau ($\oplus$):

Bukti bergelombang: A $\oplus$ tidak pernah memerlukan lebih banyak bit dari inputnya, jadi itu berarti bahwa tidak ada hasil antara di atas membutuhkan lebih dari bit maksimum input (jadi $O(\log_2 n)$ bit). $\oplus$ bersifat komutatif, dan $x \oplus x = 0$, jadi jika Anda memperluas yang di atas dan memasangkan semua data yang ada dalam aliran Anda akan dibiarkan hanya dengan satu nilai yang tidak cocok, angka yang hilang.

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