Код Middle Биты обновлено
Единственное непарное число
Условие
Все числа встречаются дважды, кроме одного. Найди его за O(n) времени и O(1) памяти.
Примеры
singleNumber([2, 2, 1]) // 1
singleNumber([4, 1, 2, 1, 2]) // 4
singleNumber([7]) // 7
Как подойти
XOR как приём: a ^ a === 0 и a ^ 0 === a, поэтому все пары взаимно уничтожаются. Решение через Set корректно, но тратит O(n) памяти - а условие требует O(1), и именно это здесь проверяют.
Подсказки: 2
- Исключающее ИЛИ числа с самим собой даёт ноль.
- Операция коммутативна - порядок не важен.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.