Нахождение единственного числа в массиве

Условие

Дан массив arr, содержащий нечётное количество целых чисел. Каждое значение встречается ровно дважды, за исключением одного — единственного, которое присутствует лишь один раз. Необходимо определить и вернуть это единственное число.

void findUnique(const std::vector<int>& arr) {
    // найти элемент, который встречается один раз
}

Пример:

Вход: [2, 3, 5, 4, 5, 3, 4]
Выход: 2

Ответ

Вычислите XOR всех элементов: одинаковые пары обнулятся, и останется единственное непарное число. Алгоритм использует O(n) времени и O(1) памяти.

Чтобы вернуть значение, замените void на int:

int findUnique(const std::vector<int>& arr) {
    int result = 0;
    for (int value : arr) result ^= value;
    return result;
}

Для примера получится 2. Метод опирается на условие «все остальные встречаются ровно дважды»; он не проверяет это условие. При произвольных частотах полученный XOR может вообще не быть искомым уникальным элементом.