Znaleźć brakującą liczbę

0

Wczoraj na imprezie usłyszałem zadanie typu:
mamy 50 liczb: 1,2,3...50

ktoś daje mi zbiór 49 liczb pomieszanych.... jak najłatwiej (za pomocą jednego przejrzenia tablicy) znaleźć tą brakującą?
Pytanie 2: to samo, tyle że brakuje 2-ch liczb

Gryzie mnie to strasznie, a ponoć jest to jakieś znane zadanie (choć google nie chce mi pomóc w jego znalezieniu)

0

zadanie NOE ze SPOJa (fajne)
wystarczy informacja, że da się liniowo. Warto samemu na to wpaść.
a gdy brakuje dwu... hym

0

Częste w zadaniach wymaganie by tylko raz przeglądać tablicę wejściową można łatwo obejść. Na przykład w tym zadaniu można to zrobić tak:

String s="";
for(int i=0;i<49;i++)
   s=s+" "+tab[i];

a potem analizować String s.
Ograniczenie powinno być inaczej formułowane. Może tak: można użyć tylko jednej pętli?

0

Tzn...
Pierwsza część zadania łatwa... zsumować wszystkie i sprawdzić z sumą całej tablicy, ale pytanie o 2 elementy sprawiło, że zacząłem myśleć czy aby nie ma innego algorytmu który sprawdzi się w każdym wypadku

0

przetestowałem tylko na 100'000'000 losowo wykreślonych par i wygląda OK

0

Czy zapisywanie na 64 bitowej wartości numery bitów, które się pojawiły jest oszustwem?
Np.:

std::map<unsigned long long, std::pair<unsigned, unsigned> > m;

void preprocess() {
for(unsigned i = 1; i <= 50; ++i)
for(unsigned j = i+1; j <= 50; ++j)
m[~((1ULL << i) | (1ULL << j))] = std::make_pair<unsigned, unsigned>(i, j);
}

std::pair<unsigned, unsigned> policz() {
unsigned long long num = 0;
unsigned x;
while(load(x)) num |= 1ULL << x;

return m[num];
}

Plus jest taki, że da się uogólnić tak na oko do 6 brakujących liczb

0

Według mnie chodzi tylko o przejście raz przez tablice
#

#include <cstdio>

int main()
{
    int tab[4] = {0, 1, 3, 2};
    bool tab2[5];

    for(int i = 0; i < 5; i++)
        tab2[i] = false;

    for(int i = 0; i < 4; i++)
        tab2[tab[i]] = true;

    for(int i = 0; i < 5; i++)
        if(tab2[i] == false)
            printf("%d\n", i );

    return 0;
}
0

to też kopia, w sumie nie było, że nie wolno
z różnicy sum mamy kilka rozwiązań (1..49), dodałem kwitnący filtr

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0