Задача с собеседования в Zomato

Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно два раза. Найдите два элемента, которые появляются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает за линейное время и использует только константное дополнительное пространство.

Пример 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] - также валидный ответ.

Пример 2:
Input: nums = [-1,0]
Output: [-1,0]

Пример 3:
Input: nums = [0,1]
Output: [1,0]

Ограничения:
2 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Каждое число в nums встретится два раза, только два числа встретятся один раз.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Более сложный вариант задачи на использование побитового оператора XOR (исключающего ИЛИ), сравнивающего два бита:
- если биты одинаковые -> 0
- если биты разные -> 1

Применяем XOR для "обнуления" всех чисел в массиве, которые встречаются два раза, используя свойства: a ^ a = 0 и a ^ 0 = a. Предварительная сортировка не требуется, так как a ^ b = b ^ a.
- проходим по массиву nums, накапливая XOR всех эл-в. Таким образом, получим XOR = a ^ b, где a и b - искомые числа.

Теперь у нас есть некоторое значение XOR, хранящееся в двоичном виде.
Предлагаю разобрать подробнее на примере 1: после первого прохода XOR = 3 ^ 5 = 6. В двоичном виде это выглядит следующим образом:
3 = 0 1 1
5 = 1 0 1
6 = 1 1 0

Единицы находятся в тех разрядах, где биты у a и b различаются => можем использовать какой-либо из этих разрядов в качестве разделителя. Найдём самый младший единичный бит с помощью цикла while:
Пока XOR & diff_bit равно нулю:
- ищем единичный бит, перебирая битовые позиции справа налево с помощью переменной diff_bit, сдвигая единицу из младшего разряда в старший.
На примере XOR = 6 (110):
diff_bit = 1 (001): 110 & 001 = 0
diff_bit = 2 (010): 110 & 010 = 2 => нужный бит найден - второй разряд справа.

Также для нахождения младшего единичного бита-разделителя можно было бы использовать формулу: diff_bit = xor & -xor (рекомендую почитать о «дополнительном коде»).

Таким образом, зная разделяющий бит, можем использовать его для распределения чисел по двум группам.
Проходим по массиву nums, проверяя для каждого числа:
- если diff_bit & текущее число не равно нулю => у числа стоит 1 в том же разряде, что и у diff_bit;
- иначе => стоит 0.
Уникальные числа a и b различаются в выбранном бите, а значит, попадут в разные группы. Парные же числа, имея одинаковые биты, попадут в одну и ту же группу и «обнулятся» при операции XOR. В каждой группе останется одно искомое число.

Выводим найденные числа в виде массива.

Сложность
O(n) - по времени (проходим двумя циклами по n элементам)
O(1) - по памяти (храним целочисленные переменные xor, diff_bit, a, b)

Код
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for n in nums:
xor ^= n

diff_bit = 1
while not(xor & diff_bit):
diff_bit = diff_bit << 1

a, b = 0, 0
for n in nums:
if diff_bit & n:
a = a ^ n
else:
b = b ^ n

return [a, b]

@algoses