Solution to "Googol String" Code Jam problem

googol_string.py

"""
https://code.google.com/codejam/contest/4284486/dashboard

Key insight: any digit in S_googol is ultimately a reversal/switch
of a zero that was inserted between two strings. If we can somehow
count the number of switches, then we'll know whether the digit is
a 1 or 0.

Knowing the position of these middle zeros and reverse-engineering
the reversals from a given index to an index of one of the middle
zeros will allow us to count the number of switches.
"""


from bisect import bisect_left


def get_middle_zero_indices():
    k_limit = 10**18

    def _generate_middle_zero_indices():
        i = 0

        while i < k_limit:
            yield i
            i = 2*i + 1

    return tuple(_generate_middle_zero_indices())


def get_digit(k, middle_zero_indices):
    switches = 0

    while True:
        i = bisect_left(middle_zero_indices, k)

        if i < len(middle_zero_indices) and middle_zero_indices[i] == k:
            return switches % 2
        else:
            mzi = middle_zero_indices[i-1]
            k = mzi - (k - mzi)  # reversal around a middle zero
            switches += 1


def main():
    middle_zero_indices = get_middle_zero_indices()
    T = int(raw_input())

    for t in xrange(1, T+1):
        k = int(raw_input()) - 1  # convert from 1-based to 0-based index
        print 'Case #{}: {}'.format(t, get_digit(k, middle_zero_indices))


if __name__ == '__main__':
    main()