А вот задачка на выходные! Она плохо подходит, чтобы спрашивать на собеседовании, потому что слишком уж на инсайт (пожалуйста, никогда не задавайте такие на собеседованиях), и слишком простая для соревнований. Как раз чтобы доставить тот самый satisfying click в мозгу, за который мы любим программирование. Итак:
Не забывайте использовать тег <spoiler> для решений в комментариях!
тривиальное решение: заводим нулевой битовый массив на 4Г битов (константная память!). если мы видим какое-то число то делаем на его позиции исключающее или с единицей. в конце только два бита будут равны одному — это и есть те числа что мы искали. в один проход по дополнительному массиву можно их найти.
Не троллить :) Давайте, чтобы не было разночтений — памяти у вас четыре килобайта.
В комментариях тоже много решений, с кодом и без, вот некоторые (список не претендует на полноту):
Решение от kmu1990
Решение от Ogra
Решение от ZyXI
Как решали бы задачу в стартапе от Demogor
Развитие задачи от deniskreshikhin
Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com, отсюда и стиль изложения, и наличие уточняющих вопросов.
Есть большой массив из N 32-битных чисел. Каждое число встречается два раза, а два числа -- по одному. Найти эти два числа за один проход по массиву с константными затратами памяти (то есть не зависящими от размера массива).Не забывайте использовать тег <spoiler> для решений в комментариях!
тривиальное решение: заводим нулевой битовый массив на 4Г битов (константная память!). если мы видим какое-то число то делаем на его позиции исключающее или с единицей. в конце только два бита будут равны одному — это и есть те числа что мы искали. в один проход по дополнительному массиву можно их найти.
Не троллить :) Давайте, чтобы не было разночтений — памяти у вас четыре килобайта.
Одно из решений
Как легко заметить, парные числа намекают, что задача про xor!
Пусть искомые числа — X и Y. Если просто сделать xor всех чисел в массиве, понятно что результатом будет X^Y, что хорошо тем, что все другие числа сократились, но плохо тем, что возможности их вычислить не дает. Что делать?
Заметим, что если бы мы заранее знали в каком бите числа X и Y отличаются (а такой бит быть обязан), то задача бы решалась просто — давайте сделаем xor всех чисел, у которых в бите N скажем единица. Все парные числа сократятся, и результатом будет X или Y. А если у нас есть еще и значение X^Y, то и второе число просто вычислить.
Более того, если у нас есть X^Y это еще и говорит, в каком бите X и Y отличаются — там где в xor 1.
Осталось понять как это сделать за один проход.
Давайте во время прохода насчитывать xor всех чисел и 32 аккумулятора. В i-ом аккумуляторе мы будем накапливать xor всех чисел, у которых 1 в i-м бите. В конце воспользуемся одним из аккумуляторов, где биты различаются.
Пусть искомые числа — X и Y. Если просто сделать xor всех чисел в массиве, понятно что результатом будет X^Y, что хорошо тем, что все другие числа сократились, но плохо тем, что возможности их вычислить не дает. Что делать?
Заметим, что если бы мы заранее знали в каком бите числа X и Y отличаются (а такой бит быть обязан), то задача бы решалась просто — давайте сделаем xor всех чисел, у которых в бите N скажем единица. Все парные числа сократятся, и результатом будет X или Y. А если у нас есть еще и значение X^Y, то и второе число просто вычислить.
Более того, если у нас есть X^Y это еще и говорит, в каком бите X и Y отличаются — там где в xor 1.
Осталось понять как это сделать за один проход.
Давайте во время прохода насчитывать xor всех чисел и 32 аккумулятора. В i-ом аккумуляторе мы будем накапливать xor всех чисел, у которых 1 в i-м бите. В конце воспользуемся одним из аккумуляторов, где биты различаются.
В комментариях тоже много решений, с кодом и без, вот некоторые (список не претендует на полноту):
Решение от kmu1990
Решение от Ogra
Решение от ZyXI
Как решали бы задачу в стартапе от Demogor
Развитие задачи от deniskreshikhin
Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com, отсюда и стиль изложения, и наличие уточняющих вопросов.
