Как оптимизировать алгоритм поиска уникального элемента без дополнительной памяти

Что проверяют

Знаете ли вы приём с XOR и, главное, понимаете ли условия, при которых он работает. Следом обычно меняют условие: остальные элементы встречаются трижды или уникальных два.

Как отвечать

Начните с постановки: все элементы, кроме одного, встречаются ровно дважды. Наивные решения платят памятью или временем: array_count_values() строит хэш-таблицу, а sort() портит исходный массив и стоит O(n log n).

Решение за O(n) времени и O(1) памяти опирается на свойства XOR: a ^ a = 0, a ^ 0 = a, операция коммутативна и ассоциативна. Прогоните через ^ все элементы, пары обнулятся в любом порядке, останется уникальный:

• цикл: $x = 0; foreach ($arr as $v) { $x ^= $v; };
• однострочник: array_reduce($arr, fn($c, $v) => $c ^ $v, 0), стрелочные функции есть с PHP 7.4.

Затем покажите, что знаете вариации:

• остальные встречаются трижды: XOR не работает. Считают единицы в каждом бите по модулю 3 или ведут две маски ones и twos;
• два уникальных элемента: XOR всего массива даёт a ^ b. Берут любой установленный бит, например $d & -$d, делят массив на две группы по этому биту и считают XOR в каждой отдельно;
• массив отсортирован: бинарный поиск первой «сломанной» пары даёт O(log n);
• пропущенное число от 1 до n: тот же XOR индексов и значений или сумма арифметической прогрессии.

Где спотыкаются

Не проговаривают ограничение «остальные ровно дважды». Если число встречается трижды, XOR молча вернёт неверный ответ.

Забывают про типы в PHP. Если оба операнда строки, ^ работает побайтово по кодам символов: '5' ^ '3' даёт управляющий символ, а не 6. Когда накопитель начинают не с 0, а с первого элемента, и данные пришли из CSV или формы строками, результат будет мусором. Приводите значения через array_map('intval', $arr).

Экономят память сортировкой на месте и не говорят, что это портит входные данные и уже не O(n).