Задача 102946

Тема:    [ Задачи с целыми числами ]

Сложность: 3- Классы: Название задачи: ХитрОе жюRи .

Условие

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

Входные данные
Входной двоичный файл содержит последовательность 32-битовых целых чисел со знаком (File Of LongInt).

Выходные данные
Выведите в выходной текстовый файл искомое число.

Пример входного файла
XXYYXYXYXXYY

Пример выходного файла
1498962264

Решение

Рассмотрим xor-сумму всех чисел, т.е. выражение a₁ xor a₂ xor ... xor a_n , где a₁, a₂, ..., a_n –числа, записанные во входном файле. Полученный результат будет равен искомому числу.

Действительно, a xor a = 0 и 0 xor a = a. В силу коммутативности и ассоциативности операции xor (проверьте эти свойства!) можно считать, что мы сначала выполнили xor тех чисел, которые встречаются дважды. В результате указанное выражение примет вид 

(b₁ xor b₁) xor (b₂ xor b₂) xor ... xor (b_{n div 2} xor b_{n div 2}) xor с = с,

где b_i – числа, которые встречаются в файле два раза, а c – один раз.

Источники и прецеденты использования

книга
предмет	информатика
Автор	Беров В., Лапунов А., Матюхин В., Пономарев А.
Название	Особенности национальных задач по информатике
Издательство	Триада-С
Год издания	2000
глава
Номер	6
Название	Задачи на разные темы
Задача
Номер	1