Определите недостающее число в потоке данных

Question

Мы получаем поток $ n-1 $ в паре разных номеров от набора $ left {1, dots, n right } $.

Как я могу определить недостающий номер с помощью алгоритма, который один раз считывает поток и использует память только $ O ( log_2 n) $ битов?

Answer 1

Вы знаете $ sum_ {i = 1}^ni = frac {n (n+1)} {2} $, и потому что $ s = frac {n (n+1)} {2} $ можно кодировать В $ o ( log (n)) $ bits это можно сделать в памяти $ o ( log n) $ и в одном пути (просто найдите $ s - mathrm {currentsum} $, это отсутствует номер).

Но эта проблема может быть решена в общем случае (для постоянного $ k $): у нас нет числа $ k $, выяснить их все. В этом случае вместо расчета только суммы $ y_i $, рассчитайте сумму j'st with of $ 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) $

Помните, что вы можете рассчитать $ s_1, ... s_k $ просто, потому что $ s_1 = s - sum y_i $, $ s_2 = sum i^2 - sum y_i^2 $, ...

Теперь, чтобы найти пропущенные номера, вы должны решить $ (1) $, чтобы найти все $ x_i $.

Вы можете вычислить:

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

Для этого Помните это $ P_1 = s_1 $, $ p_2 = frac {s_1^2 - s_2} {2} $, ...

Но $ p_i $-это коэффициенты $ p = (x-x_1) cdot (x-x_2) cdots (x-x_k) $, но $ p $ может быть основан Уникально, так что вы можете найти недостающие числа.

Это не мои мысли; читать это.

Answer 2

Из комментария выше:

Перед обработкой потока выделяйте $ lceil log_2 n rceil $ bits, в которых вы пишете $ x: = bigoplus_ {i = 1}^n mathrm {bin} (i) $ ($ mathrm {bin} (i) $-это двоичное представление $ i $ и $ oplus $ является точечным эксклюзивным или). Наивно это требует $ mathcal {o} (n) $ время.

При обработке потока всякий раз, когда кто -то читает число $ j $, вычислите $ x: = x oplus mathrm {bin} (j) $. Пусть $ k $ будет единственным номером от $ {1, ... n } $, который не включен в поток. После прочтения всего потока у нас есть $$ 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), $$ дает желаемый результат.

Следовательно, мы использовали $ mathcal {o} ( log n) $ space и имеем общее время выполнения $ mathcal {o} (n) $.

Answer 3

Решение HDM работает. Я закодировал его в C ++, чтобы проверить его. Я не могу ограничить value до $ O ( log_2 n) $ биты, но я уверен, что вы можете легко показать, как на самом деле установлено только это количество битов.

Для тех, кто хочет псевдокода, используя простую операцию $ text {fold} $ с эксклюзивным или ($ oplus $):

$$ text {отсутствует} = text {fold} ( oplus, {1, ldots, n } cup text {inputstream}) $$

Доказывание рук: $ oplus $ никогда не требует большего количества битов, чем его вход, поэтому следует, что промежуточный результат в вышеперечисленном требует больше, чем максимальные биты ввода (так что $ o ( log_2 n) $ bits). $ oplus $ является коммутативным, и $ x oplus x = 0 $, таким образом, если вы расширите вышеизложенные и сочетаете все данные, присутствующие в потоке, вас останется только с одним не совпадающим значением, отсутствующим номером.

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