вопрос об отсутствующем элементе в массиве

Question

У меня возникла следующая проблема из алгоритма введения книги, второе издание университета МТИ

проблема следующая

Массив A [1. , n] содержит все целые числа от 0 до n, кроме одного. Было бы легко определить недостающее целое число в O (n) времени, используя вспомогательный массив B [0. , п] чтобы записать, какие числа появляются в A. В этой проблеме, однако, мы не можем получить доступ целое число в A с одной операцией. Элементы А представлены в двоичном коде, и единственная операция, которую мы можем использовать для доступа к ним, это «получить j-й бит A [I], "который занимает постоянное время.

Показать, что если мы используем только эту операцию, мы все равно можем определить отсутствующее целое число в O (n) времени

пожалуйста, помогите

Answer 1

Позвоните по отсутствующему номеру M.

Вы можете разбить ваш массив на две части в зависимости от того, является ли младший значащий бит A[i] 1 или 0. Меньшая из двух частей (назовите это P_1) не более (n-1)/2 элементов size, и он сообщает вам, является ли младший значащий бит M 1 или 0.

Теперь рассмотрим 2-й бит для элементов P_1. Опять же, эта часть может быть разделена на две части, и меньшая из двух частей (P_2) говорит вам, должен ли этот бит быть 1 или 0.

Продолжайте (P_3, P_4, ...), пока не поймете, что такое все биты.

Вы можете доказать, что это O(n), потому что вы по сути смотрите на n + n/2 + n/4 + ... различные отдельные биты в вашем массиве, и эта сумма меньше 2n.

Answer 2

Вот реализация Python:

def bit_at(n, bit):
    return (n>>bit) & 1

def find_missing(a, bits):

    indexes = range(len(a))
    missing = 0

    for bit in range(bits):

        ones = [i for i in indexes if bit_at(a[i], bit)==1]
        zeroes = [i for i in indexes if bit_at(a[i], bit)==0]

        if len(ones) <= len(zeroes):
            indexes = ones
            missing |= (1<<bit) 
        else:
            indexes = zeroes

    return missing

print find_missing([7,2,6,4,1,5,0], 3)