aboutsummaryrefslogtreecommitdiff
path: root/find_kth_bit_nth_bin_str.py
blob: afcac248dae2c5ea577c8f9f700067a6995b2838 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 1545. Find Kth Bit in Nth Binary String

"""
given two positive integers 'n' and 'k', the binary string 's_n' is formed as
follows: 's_1 = 0', 's_i = s_i - 1 + "1" + reverse(invert(s_i - 1))' for 'i >
1'. where '+' denotes the concatenation operation, 'reverse(x)' returns the
reversed string 'x', and 'invert(x)' inverts all teh bits in 'x'. return the
k'th bit in 's_n'. it is guaranteed that 'k' is valid for the given 'n'.
"""


class Solution(object):
    def findKthBit(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        flip = 0
        inv = 2**n - 1
        while k > 1:
            if k == inv / 2 + 1:
                return str(1 ^ flip)
            if k > inv / 2:
                k = inv + 1 - k
                flip = 1 - flip
            inv /= 2
        return str(flip)


if __name__ == "__main__":
    obj = Solution()
    print(obj.findKthBit(3, 1))
    print(obj.findKthBit(4, 11))