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