Задача

Продолжаем рубрику #задачки, где мы разбираем интересные задачи из мира программирования и не только. Сегодня на очереди довольно интересная задачка, которая сформулирована очень просто и просто решается большинством из нас. Однако в ней зарыт демон - и он заберет у вас пальцы, если вы не решите ее за линейное время и константную сложность по памяти. Как вы тогда код писать будете? То-то же. Придется решать.

Формулировка такая: дан непустой массив интов. Каждый элемент массива встречается ровно 2 раза, кроме одного, который встречается 1 раз. Необходимо найти этот элемент.

Напоминаю правила: под этим постом проходят все обсуждения возможного решения задачи. Знающих решение прошу воздержаться от комментирования. Вечером выйдет пост с решением, где можно уже обсуждать все, что угодно, касаемо задачи и не только.

Всем удачи и погнали решать!

Challenge your life. Stay cool.