Баянистая задача, которую нужно знать всем.

Дается набор неотрицательных чисел. Известно, что каждое число встречается два раза, кроме одного числа, которое встречается один раз. Найдите число которое встречается один раз. (не использовать словари и дополнительный массив)

Решение:
Воспользуемся фактом а XOR a = 0. Если мы проискорим все числа из массива получил в результате число которое встречалось один раз, так как все числа которые встречались два раза убьются.
Время работы О(N)