Kvark161's blog

By Kvark161, 11 years ago, In Russian

Задача: В очень большом целочисленном массиве (n > 10^9, |ai| <= 10^18) найти число, которое не повторяется (гарантируется, что оно есть и такое единственное).

Пример ввода:

7 11 26 7 11

вывод:

26

Если повторов каждого числа четное количество (кроме одного, которое нужно найти), то можно применить XOR последовательно ко всем элементам. А как можно быстро найти искомый элемент, если числа могут повторяться нечетное количество раз.

Пример ввода:

1 17 5 17 1 17

вывод:

5

UPD: Числа можно считывать повторно, они хранятся в файле, с которым можно делать все, что хочется. Ограничений на время и память нет.

  • Vote: I like it
  • +16
  • Vote: I do not like it