Find Kth Bit in Nth Binary String — LeetCode 1545 Python Solution

The problem

Given two positive integers n and k, the binary string Sn is formed as follows: S1 = "0" Si = Si - 1 + "1" + reverse(invert(Si - 1)) for i > 1 Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0). For example, the first four strings in the above sequence are: S1 = "0" S2 = "011" S3 = "0111001" S4 = "011100110110001" Return the kth bit in Sn.

Example

Input

n = 3, k = 1

Output

"0"

Explanation

S3 is "0111001".

Python solution

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def dfs(n: int, k: int) -> int:
            if k == 1:
                return 0
            if (k & (k - 1)) == 0:
                return 1
            m = 1 << n
            if k * 2 < m - 1:
                return dfs(n - 1, k)
            return dfs(n - 1, m - k) ^ 1

        return str(dfs(n, k))

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1545. Find Kth Bit in Nth Binary String is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems