Solution to following problem: Array A contains all integers from 0 to n, except one is missing. In this problem we cannot access an entire integer in A in a single op. The elements of A are represented in binary, and the only op we can use is “fetch the jth bit of A[i],” which takes constant time. Write code to find the missing integer. Can you…

find_missing_value.py

####################################
# Copyright Christopher Abiad, 2013
# All Rights Reserved
####################################

__author__ = 'Christopher Abiad'

def find_missing_one(bit_index, A):
    # there is only one item
    if bit_index == 0:
        assert(len(A) == 1)
        if A[0][bit_index] == 1:
            return 0
        else:
            return 1

    zero_list = []
    one_list = []
    for item in A:
        if item[bit_index] == 0:
            zero_list.append(item)
        else:
            one_list.append(item)

    limit = 2 ** bit_index

    if len(zero_list) == limit:
        cur_missing_bit = 1
        l = one_list
    else:
        cur_missing_bit = 0
        l = zero_list

    return (2 ** bit_index) * cur_missing_bit + \
        find_missing_one(bit_index - 1, l)

from math import ceil, log
def next_power_of_2(val):
    return 2 ** int(ceil(log(val, 2)))

if __name__ == '__main__':
    # NOTE: bit indices are reversed. 4 (100) is missing and
    # would have been stored as [0,0,1] in A.
    A = [[0,0,0], [1,0,0], [0,1,0], [1,1,0], [1,0,1], [0,1,1]]
    bit_index = int(log(next_power_of_2(len(A)), 2)) - 1
    print find_missing_one(bit_index, A)