Разбор задачи «Таинственный жетон»

Идея задачи

Нам дан массив чисел. Известно, что каждое число встречается ровно два раза, кроме одного числа, которое встречается ровно один раз.

Нужно найти это число.

Например, если дан массив:

4 1 2 1 2

то ответ равен 4, потому что числа 1 и 2 встречаются по два раза, а число 4 — один раз.

Наивная идея

Первое, что может прийти в голову, — посчитать количество вхождений каждого числа.

Такой способ действительно работает, но требует дополнительной памяти для хранения частот.

Однако в этой задаче есть гораздо более красивое решение, которое работает:

• за линейное время;
• без дополнительных структур данных;
• с постоянной дополнительной памятью.

Ключевая идея: операция XOR

Будем использовать побитовое исключающее ИЛИ, то есть операцию xor.

В C++ это оператор ^, в Python — тоже ^.

У xor есть три очень важных свойства:

1. a ^ a = 0
2. a ^ 0 = a

3. Порядок вычисления не важен:

   • a ^ b = b ^ a
   • (a ^ b) ^ c = a ^ (b ^ c)

Из этих свойств следует очень важный вывод:

если какое-то число встречается дважды, то при последовательном xor оно уничтожается.

Например:

5 ^ 5 = 0

12 ^ 12 = 0

Значит, если мы возьмем xor всех элементов массива, то все парные числа сократятся, и останется только число без пары.

Как это работает на примере

Рассмотрим массив:

4 1 2 1 2

Посчитаем xor всех элементов:

4 ^ 1 ^ 2 ^ 1 ^ 2

Перегруппируем одинаковые числа:

4 ^ (1 ^ 1) ^ (2 ^ 2)

Теперь применим свойство a ^ a = 0:

4 ^ 0 ^ 0

Остается:

4

Это и есть ответ.

Алгоритм

1. Заводим переменную ans = 0.

2. Проходим по всем элементам массива.

3. Для каждого элемента выполняем:

   ans = ans ^ x

4. После завершения цикла в ans будет храниться число, которое встретилось один раз.

Почему алгоритм правильный

Докажем корректность.

Пусть в массиве есть числа, которые встречаются по два раза, и одно число u, которое встречается один раз.

Тогда xor всех элементов массива можно записать так:

a1 ^ a1 ^ a2 ^ a2 ^ ... ^ ak ^ ak ^ u

Так как для любого числа x верно x ^ x = 0, все пары превращаются в ноль:

0 ^ 0 ^ ... ^ 0 ^ u

Так как 0 ^ u = u, в результате остается число u.

Следовательно, алгоритм действительно находит единственное число без пары.

Оценка сложности

Мы один раз проходим по массиву из n элементов.

Время

O(n)

Дополнительная память

O(1)

Это оптимальное решение, потому что все элементы массива все равно нужно хотя бы один раз прочитать.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ans ^= x;
    }

    cout << ans << '\n';
    return 0;
}

Реализация на Python

n = int(input())
a = list(map(int, input().split()))

ans = 0
for x in a:
    ans ^= x

print(ans)

Пошаговый разбор работы программы

Пусть входные данные такие:

5
4 1 2 1 2

Тогда переменная ans будет изменяться так:

• сначала ans = 0
• после 4: ans = 0 ^ 4 = 4
• после 1: ans = 4 ^ 1
• после 2: ans = 4 ^ 1 ^ 2
• после второго 1: пары 1 ^ 1 уничтожаются
• после второго 2: пары 2 ^ 2 уничтожаются

В итоге остается 4.

Частые ошибки

1. Использовать сумму вместо xor

Если складывать числа, одинаковые элементы не будут сокращаться.

Например:

1 + 1 = 2, а не 0.

Поэтому здесь нужна именно операция xor.

2. Неправильно считать входные данные

Важно не забыть считать:

• сначала число n;
• затем n элементов массива.

3. Пытаться сортировать массив

Сортировка тоже может помочь решить задачу, но это будет медленнее:

• сортировка работает за O(n log n);
• решение через xor работает за O(n).

Поэтому здесь лучше использовать именно побитовую операцию.

Вывод

В этой задаче нужно заметить специальное свойство:

• все числа, встречающиеся дважды, можно взаимно уничтожить;
• операция xor делает это автоматически.

Именно поэтому решение получается очень коротким и эффективным.

Главная мысль задачи:

если все элементы, кроме одного, встречаются дважды, то xor всех элементов массива равен этому единственному элементу.

Это важная и очень полезная идея, которая часто встречается в задачах на битовые операции.