кроссворды, задачки, головоломки

Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи.

Petruchek.Info

Найти непарное число

Добавлено: 27.08.10 в 12:10
Метки: информатика

a) Есть очень большой файл, в котором лежит очень много (точнее, 2n+1) целых 64-битных чисел. Известно, что в нем n пар одинаковых чисел, и еще одно "непарное".

Требуется найти это самое "непарное" число за O(n) времени и O(1) памяти.

Естественно, числа в паре не обязательно идут подряд - иначе было бы слишком просто.

б) То же самое, но чисел 2n+2, и непарными являются два из них. Требуется найти оба.

У этой задачи пока что нет ответа/решения. Вы можете прислать свой вариант в комментарии.

источник

Комментарии
Google says:
Аноним (03.12.10):
с помощью деления по модулю 2, т.е. xor, для первого случая.
kolun (15.06.11):
Как сказал Аноним, для нахождения одного непарного числа достаточно сложить все числа по модулю 2.

Для нахождения 2х непарных чисел потребуется массив из 64 (от 0 до 63 элемента) чисел.
Примем, что первое непарное число равно А, второе В. Операцию сложения по модулю 2 обозначим ^.
К i числу будем прибовлять по модулю 2 (xor) число, в котором i-ый бит равен 1. В итоге в каждом (i-ом) из чисел будет:
а) 0, если в А и В в i-ом бите 0
б) число А, если в А в i-ом бите 1, а в В - 0
в) число В, если в В в i-ом бите 1, а в А - 0
г) число А^В, если в А и В в i-ом бите 1 (в этом случае в (А^В) в i-ом бите будет 0)

Теперь проверяем каждое число. Если в i-ом числе в i-ом бите 1, то это непарное число. Если 0, то это число либо это 0, либо (А^В).

Возможно три случая:
а) Нашли два непарных числа - Profit
б) Нашли одно непарное число (пусть будет А) и (А^В). Тогда В = А ^ (А^В). Profit. Этот вариант возможен когда все единичные биты В содержатся в А.
в) Нашли одно непарное число, а остальные 0. Тогда В = 0.
Комментарий от новенького:
Новенький является
Новенький не робот
Знаки на картинке: латинские буквы, арабские цифры


Есть на сайте: Онлайн кроссворды Задачи Онлайн игры Блог
Все работы, опубликованные на сайте — авторские, если не указано иное. Перепечатка возможна только с письменного разрешения владельцев ресурса, с обязательной ссылкой на сайт petruchek.info. Пишите нам: . Сайт должен работать в IE, FF, Opera, Safari.

Реклама:

Разработано в студии "Webous"о проектесайта карта

Реклама: