8736. Arka Noego [NOE]

Zadanie:
https://pl.spoj.com/problems/NOE

Skrócony opis zadania:

Mając $n$ liczb z przedziału $\left<1;10^9\right>$ znajdź liczbę, która nie ma pary (wszystkie pozostałe mają).

Np. dla liczb: 1 2 3 2 1 wynik to 3, gdyż 1 i 2 mają pary.

Rozwiązanie naiwne:

Możemy dla każdego elementu sprawdzać wszystkie pozostałe i jeśli nie znajdziemy żadnego do pary to robić breaka i go wypisać.

Złożoność: $O(n^2)$, bo dla każdego z $n$ liczb sprawdzamy $n-1$ pozostałych.

Rozwiązanie sprytniejsze:

Możemy mapować te elementy. Czyli innymi słowy mamy sobie tablicę haszującą $tab$, która na początku jest pusta. Następnie dla każdej liczby $x$ wykonujemy $++tab[x]$. Po przejściu wszystkich elementów sprawdzamy, która komórka ma wartość 1 i wypisujemy jej klucz.

Złożoność: $O(n \log n)$, jeśli użyjemy mapy z STLa. Przy użyciu dobrej tablicy haszującej, która dodaje elementy w czasie stałym nadal będzie to $O(n \log n)$, gdyż będziemy musieli przejść całą tę tablicę.

Rozwiązanie sprytniejsze nr 2:

Możemy posortować liczby z wejścia. Następnie przechodzimy je od początku (lub końca - obojętnie) i sprawdzamy kolejne pary liczb. Jeśli pierwsza liczba z pary nie jest równa drugiej, to wypisujemy tę pierwszą. Jeśli przejdziemy całą tablicę i nie napotkamy takiej "nierównej" pary, to wypisujemy ostatnią liczbę.

Np. dla powyższego przykładu: 1 2 3 2 1 po posortowaniu liczby będą wyglądać tak: 1 1 2 2 3. Jak widać po przejściu całej tablicy okaże się, że wszystkie pary się zgadzają, więc wypisujemy jedyną liczbę bez pary, czyli tę ostatnią.

Wadą tego rozwiązania jest zależność od $n$. Jeśli $n$ jest duże, to nie będziemy mogli stablicować wszystkich liczb, gdyż nie starczy nam pamięci. Najlepsze rozwiązanie jest niezależne pamięciowo od $n$.

Złożoność: $O(n \log n)$, ze względu na sortowanie.

Rozwiązanie najsprytniejsze:

Możemy też coś zaobserwować. Mamy zawsze pary liczb i tylko jedną nie do pary. Moglibyśmy zatem użyć jednej z tych liczb do anulowania drugiej. Tzn. jeżeli pojawi się pierwsza liczba, to jest coś ustawiane, a kiedy pojawi się druga, to jest to resetowane. Taką właśnie operacją jest XOR (symbol $\oplus$). Jeśli ktoś nie wie, $x \oplus x = 0$ (bo para bitów na każdej pozycji jest taka sama, co zwraca dla każdej pozycji 0). Ponadto $0 \oplus x = x$. Tak więc możemy po prostu ustawić zmienną $x$ na 0, a potem dla każdej z $n$ liczb wykonywać $x \oplus= a_i$ (gdzie $a_i$ to kolejna liczba z wejścia). Na końcu wszystkie pary się anulują i zostanie jedna liczba będąca tą bez pary.

Złożoność: $O(n)$, bo dla każdej liczby wykonujemy tylko jedną operację. Kolejną zaletą tego rozwiązania jest niezależność od pamięci - złożoność pamięciowa to $O(1)$.

Ostateczny algorytm:

int main()
{
    int x = 0, y;
    while(get(y))
        x ^= y; // ^ to operator XOR w C/C++
    print(x);
}