Единственное непарное число: решение через XOR

Условие

//Дан массив чисел, в котором все числа кроме одного имеют пару, //найти число, которое встречается только один раз

// <= [1, 0, 3, -2, 9, 9, 1, -2, 0] // => 3

Ответ

Используйте XOR всех элементов: x ^ x = 0, а 0 ^ x = x. Парные значения сократятся, и останется единственное непарное число — в примере 3.

public int singleNumber(int[] values) {
    int result = 0;
    for (int value : values) {
        result ^= value;
    }
    return result;
}

Время O(n), дополнительная память O(1). Метод работает и с отрицательными int. Он опирается на условие: ровно одно значение встречается один раз, остальные — парами. Для произвольных частот или проверки корректности входа нужен другой контракт, например подсчёт частот.