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

Автор: admin от 31-08-2017, 17:31, посмотрело: 537

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

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

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

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

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

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

Источник: Хабрахабр

Категория: Программирование

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *