Leetcode 1667 Solution

This article provides solution to leetcode question 1667 (find-kth-bit-in-nth-binary-string)
Categories:
Tags:
Access this page by simply typing in "lcs 1667" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/find-kth-bit-in-nth-binary-string

Solution

class Solution:
    def invert(self, ch):
        if ch == '0':
            return '1'
        elif ch == '1':
            return '0'

    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return "0"

        s_len = pow(2, n) - 1

        k -= 1

        if k == s_len // 2:
            return "1"
        elif k < s_len // 2:
            return self.findKthBit(n - 1, k + 1)
        else:
            return self.invert(self.findKthBit(n - 1, s_len - k))