Здравствуйте fAX, Вы писали:

fAX>Из одного моего экзамена.

fAX>Есть read-only массив из n элементов (чисел), каждый из которых состоит из [log n](верхняя граница) битов. Единственно, что известно, что в массиве находятся числа от одного до n, кроме одного (произвольного) числа в произвольном порядке. За один раз можно прочитать только один бит одного элемента массива. Нужно за O(n) определить, какого числа не хватает. Можно использовать O(n) памяти.

fAX>Удачи.
fAX>ЗЫ. Было давно, так что не гарантирую правильность условий, но, вроде, всё правильно.

Для простоты предположим что n — степень числа 2 (если нет — можем расширить массив, дописав в конец соотвествующие числа, что потребует не более че О(n) времяни и памяти).

1. Просматриваем старшие биты массива, одновременно составляем массив и индексов, тех элементов массва, которые содежат "1" в старшем бите, и массив с "0" в старшем бите. Подсчитываем число элементов у которых в старшем бите — 1. Если число элементов с "1" в старшем бите равно n/2-1, значит нехватает числа в котором этот бит взведен, если n/2, то наоборот.
2. Просматриваем те числа массива, у которых первы бит имеет заданое состояние. (массив положений таких чисел, получен на предыдущем шаге). Просматриваем второй бит, формируе массивы где данный бит взеден и не взведен, подсчитывем число взведенных. ...
3. Анализируем третий бит ...
...


на первом шаге алгоритма n — чтений,
на втором — n/2
всего не более 2n чтений.