А ось задачка на вихідні! Вона погано підходить, щоб просити на співбесіді, бо надто вже на інсайт (будь ласка, ніколи не задавайте такі на співбесідах), і занадто проста для змагань. Якраз щоб доставити той самий satisfying click в мозку, за який ми любимо програмування. Отже:

Є великий масив з N 32-бітових чисел. Кожне число зустрічається два рази, а два числа-по одному. Знайти ці два числа за один прохід по масиву з константними витратами пам’яті (тобто не залежать від розміру масиву).

Не забувайте використовувати тег для рішень в коментарях!

тривіальне рішення: заводимо нульовою бітовий масив на 4Г бітів (електронний пам’ять!). якщо ми бачимо якесь число, то робимо на його позиції виключає або з одиницею. в кінці тільки два біти дорівнюють одному — це і є ті числа що ми шукали. в один прохід по додатковому масиву можна їх знайти. Не троль 🙂 Давайте, щоб не було різночитань — пам’яті у вас чотири кілобайта.

Рішення буде додано, наприклад, у понеділок.

Disclaimer: пост написаний на основі неабияк відредагованих лог чату closedcircles.com, звідси і стиль викладу, та наявність уточнюючих питань.