Почему это работает
- xor переключает каждый бит result там, где в num стоит 1. Число, пришедшее дважды, переключает одни и те же биты два раза, и они возвращаются: a xor a = 0, а x xor 0 = x.
- Переключениям не важен порядок: две 10 стоят далеко друг от друга, а между ними result проходит 9, 14 и 13 — числа, которых в массиве нет. Важен только итог.
- После всех чисел бит result равен 1 ровно тогда, когда 1 в этом месте была у нечётного числа чисел. Пары дают везде чётное число, поэтому остаются биты числа без пары.
Сложность
Время O(n): один проход, по одному xor на число. Память O(1): одно число, без множества и словаря.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗