Ещё один XOR-фокус

Этот — красивый, но из серии знаешь/не знаешь. Зато основан на свойствах операции, одной ногой в алгебре!

Представьте задачу: дан массив чисел, где все элементы встречаются ровно два раза, кроме одного, который встречается один раз. Как найти этот уникальный элемент одним проходом? Чтобы и без сортировки и без дополнительной памяти?

Решение гениально простое: XOR всех элементов массива!

[5, 2, 9, 2, 5]
→ 5 ⊕ 2 ⊕ 9 ⊕ 2 ⊕ 5
 = 9

Парные элементы взаимно уничтожаются (так как A ⊕ A = 0), а уникальный остаётся.

Этот трюк работает из-за четырёх магических свойств XOR:

• Коммутативность:
  A ⊕ B = B ⊕ A
• Ассоциативность:
  (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
• Взаимное уничтожение:
  A ⊕ A = 0
• Нейтральность нуля:
  A ⊕ 0 = A

Что-то напоминает, неправда ли? Теперь и вы знаете, как решить эту задачу за собеседовании самым оптимальным, но на практике чаще всего недоступным способом 😎