Усложненный вариант задачи "ХитрОе жюРи".

[Chuckle]

"На вход подаются неотрицательные числа количеством не более 1.5 млрд, по значению не превышающие 1.5 млн. Известно, что все числа, кроме двух, встречаются ровно по 2 раза, а те два числа - по одному разу. Найти эти два числа."

Помогите пожалуйста с алгоритмом решения.

Если бы было только одно число, встречающееся один раз (нечетное количество раз), а все остальные встречались по два раза (четное количество раз), то тут всё понятно: "ксорим" все числа со входного потока, ввиду равенств a ^ 0 == a, a ^ a == 0, (a ^ b) ^ a == b легко получаем нужное число.

А как быть тут? Входной поток вводится в массив, кстати говоря. Но его нельзя сортировать. И ограничение по времени выполнения программы 1 секунда.

^ - операция побитового сложения по модулю два