Problem Statement in English

You’re given two positive integers n and k. The n-th binary string S(n) is formed by the n-1-th binary string S(n-1), followed by “1”, and then followed by the reverse of the n-1-th binary string S(n-1) with each bit inverted (0 changes to 1 and 1 changes to 0).

Return the k-th bit in S(n). The bits are 1-indexed, as is k.

Approach

You could use the naive brute force solution of generating the binary string for n and then returning the k-th bit. However, this approach is inefficient. Instead, we can use recursion to find the k-th bit without generating the entire string.

Notice that the length of S(n) is $2^n - 1$. The middle index of the string is $(\text{length of } S(n) // 2) + 1$, which is $2^{n-1}$.

There are 3 cases to consider:

  • If k is less than the middle index of the string, then the k-th bit is the same as the k-th bit in S(n-1). We don’t need to generate the entire string, we can just make a recursive call to find the k-th bit in S(n-1).

  • If k is equal to the middle index, then the k-th bit is “1”. This is because the string length is odd, and the middle bit is always “1”, as specified in the question.

  • If k is greater than the middle index, then we need to find the corresponding bit in the reversed and inverted part of the string. We can calculate the new index new_k as final_length - k + 1, where final_length is the length of S(n). The k-th bit will be “0” if the corresponding bit in S(n-1) is “1”, and “1” if it is “0”.

And we’re done!

Solution in Python


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

            final_length = pow(2, n) - 1
            mid = (final_length // 2) + 1

            if k < mid:
                return dfs(n - 1, k)
            elif k == mid:
                return "1"
            else:
                new_k = final_length - k + 1
                return "0" if dfs(n - 1, new_k) == "1" else "1"

        return dfs(n, k)

Complexity

  • Time: $O(n)$
    Since we are using recursion, the time complexity is $O(n)$ due to the depth of the recursive calls.

  • Space: $O(n)$
    Since we are using recursion, the space complexity is $O(n)$ due to the call stack.

Mistakes I Made

I implemented the naive approach of generating the binary string for n and then returning the k-th bit. This approach is inefficient even though LeetCode allows it. Had to look up this efficient approach to solve the problem.

And we are done.