А вот задачка на выходные! Она плохо подходит, чтобы спрашивать на собеседовании, потому что слишком уж на инсайт (пожалуйста, никогда не задавайте такие задачи на собеседованиях), и слишком простая для соревнований. Как раз чтобы доставить тот самый satisfying click в , за который мы любим программирование. Итак:
Есть большой массив из N 32-битных чисел. Каждое число встречается два раза, а два числа -- по одному. Найти эти два числа за один проход по массиву с константными затратами памяти (то есть не зависящими от размера массива).
Не забывайте использовать тег <spoiler> для решений в комментариях!
тривиальное решение: заводим нулевой битовый массив на 4Г битов (константная память!). если мы видим какое-то число то делаем на его позиции исключающее или с единицей. в конце только два бита будут равны одному — это и есть те числа что мы искали. в один проход по дополнительному массиву можно их найти.
Не троллить :) Давайте, чтобы не было разночтений — памяти у вас четыре килобайта.
Решение будет добавлено, например, в понедельник.
Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com, отсюда и стиль изложения, и наличие уточняющих вопросов.
Автор: sim0nsays
