LC-1545 Medium LeetCode

1545. Find Kth Bit in Nth Binary String

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 70% Topics: String, Recursion, Simulation

Reading material

Strings 12 min Backtracking 14 min Simulation & Enumeration 9 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

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

Solution from kamyu104/LeetCode-Solutions · MIT