Liczba występująca nieparzystą liczbę razy

Przypomnij sobie wyzwanie rozwiązane w lekcji „Operator XOR”, w którym wykorzystaliśmy właściwości XOR. Pytanie, które rozwiążemy w tej lekcji, jest bardzo podobne do tamtego wyzwania. Problem, którym się zajmiemy, brzmi:

Znajdź element występujący w podanej tablicy nieparzystą liczbę razy.

Otrzymasz tablicę zawierającą pewne elementy całkowite. Wszystkie elementy oprócz jednego występują parzystą liczbę razy.

Załóżmy, że mamy tablicę int Arr[11] = { 2, 5, 6, 6, 6, 4, 5, 2, 5, 4, 5}.

W tej tablicy:

• „2” pojawia się dwa razy (parzyście).
• „5” pojawia się cztery razy (parzyście).
• „6” pojawia się trzy razy (nieparzyście).
• „4” pojawia się dwa razy (parzyście).

W tym przypadku liczba „6” pojawia się nieparzystą liczbę razy. Właśnie to musimy znaleźć w tym zadaniu: liczbę, która pojawia się w tablicy nieparzystą liczbę razy.

Jak widzieliśmy w lekcji „Operator XOR”, dla liczby „x”:

• x ⊕ x = 0 (gdzie symbol „⊕” oznacza operację XOR)
• x ⊕ 0 = x

Zatem, korzystając z pierwszej właściwości, XOR elementów występujących parzystą liczbę razy da wynik 0, a dzięki drugiej właściwości pozostanie nam liczba, która wystąpiła nieparzystą liczbę razy.

Wystarczy więc wykonać XOR wszystkich elementów tablicy, aby otrzymać wynik. I to wszystko — oto rozwiązanie problemu. Proste, prawda?

Złożoność czasowa tego problemu wynosi O(n), ponieważ musimy przejść przez całą tablicę i wykonać XOR wszystkich jej elementów.