//Дан массив чисел, в котором все числа кроме одного имеют пару, //найти число, которое встречается только один раз // // // <= [1, 0, 3, -2, 9, 9, 1, -2, 0] // // => 3 int find(int[] arr){ Map<Integer,

Задача: найти единственное число в массиве, которое не имеет пары (все остальные встречаются по 2 раза).

Оптимальное решение — использовать операцию XOR (исключающее ИЛИ). Свойства XOR:

• a ^ a = 0
• a ^ 0 = a
• XOR коммутативен и ассоциативен

Поэтому, если выполнить XOR всех элементов массива, пары взаимно уничтожатся, и останется только число без пары.

Пример на Java:

int find(int[] arr) {
    int result = 0;
    for (int num : arr) {
        result ^= num;
    }
    return result;
}

// Пример использования:
// int[] arr = {1, 0, 3, -2, 9, 9, 1, -2, 0};
// find(arr) вернет 3

Это решение работает за O(n) по времени и O(1) по памяти.