четверг, 2 сентября 2010 г.

Задача о поиске недублирующихся элементов в потоке

Недавно столкнулся с еще одной интересной задачей. Звучит она так: имеется входной поток целых чисел. Известно, что в нем все элементы дублируются, кроме одного. Найти этот один элемент за константное количество проходов (O(1)) , используя константное же количество памяти.
Первоначально пришла в голову идея использовать какой-то хэш-массив, в котором ключами будут значения элементов входного потока, а значениями - число вхождений того или иного элемента в поток. Сложность в том, что заранее неизвестно, в каком диапазоне числа входного потока. Если предположить, что размер int'а 32 бита, то в хэше возможно 2^32 элементов, что, в общем, достаточно круто )
Но затем неожиданно меня посетила неплохая идея: а что, если воспользоваться операцией XOR, для которой характерны следующие правила: A XOR A = 0 и 0 XOR A = A.
Тогда просто проксорив все элементы входного потока, мы получим на выходе значение недублирующегося элемента, ибо
             A XOR B XOR A XOR C XOR B = C
То есть, для решения задачи нужен всего 1 проход по всем элементам и одна переменная, аккумулирующая результат, что, согласитесь, неплохо.

А теперь внимание. Как можно решить задачу, если в потоке не один недублирующийся элемента, а два ? Мне пока что-то ничего в голову не приходит.