Задачка про парні числа

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

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


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

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

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

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

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.