- PVSM.RU - https://www.pvsm.ru -

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

А вот задачка на выходные! Она плохо подходит, чтобы спрашивать на собеседовании, потому что слишком уж на инсайт (пожалуйста, никогда не задавайте такие задачи на собеседованиях), и слишком простая для соревнований. Как раз чтобы доставить тот самый satisfying click в мозгу [1], за который мы любим программирование. Итак:

Есть большой массив из N 32-битных чисел. Каждое число встречается два раза, а два числа -- по одному. Найти эти два числа за один проход по массиву с константными затратами памяти (то есть не зависящими от размера массива).

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

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

Решение будет добавлено, например, в понедельник.

Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com [2], отсюда и стиль изложения, и наличие уточняющих вопросов.

Автор: sim0nsays

Источник [3]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/programmirovanie/116177

Ссылки в тексте:

[1] мозгу: http://www.braintools.ru

[2] closedcircles.com: http://closedcircles.com/?invite=b4184a9d5ccf4c8db3b8992a0dace2bb73336941

[3] Источник: https://habrahabr.ru/post/280192/