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

Для оптимизации поиска уникального элемента в массиве (где все остальные элементы встречаются дважды) без использования дополнительной памяти в PHP применяется операция XOR (исключающее ИЛИ). Это возможно благодаря свойству: a ^ a = 0 и a ^ 0 = a. При последовательном XOR всех элементов массива парные значения обнуляются, а остаётся только уникальный элемент.

Пример реализации:

PHP
function findUnique(array $arr): int {
    $result = 0;
    foreach ($arr as $value) {
        $result ^= $value;
    }
    return $result;
}

// Пример использования:
$numbers = [1, 2, 3, 2, 1];
echo findUnique($numbers); // Выведет 3

Почему это оптимально:

• Временная сложность: O(n) - один проход по массиву.
• Пространственная сложность: O(1) - используется только одна переменная.
• Работает с целыми числами, включая отрицательные (в PHP XOR работает на уровне битов).

Ограничения: Метод применим только когда каждый элемент, кроме одного, встречается ровно дважды. Для других сценариев (например, три повторения) потребуется иной подход, например, сортировка или хэш-таблица, но они уже потребуют дополнительной памяти.