Code Implementation

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def helper(n, k):
            if n == 1:
                return '0'
            length = (1 << n) - 1
            mid = (length // 2) + 1
            if k == mid:
                return '1'
            elif k < mid:
                return helper(n - 1, k)
            else:
                mirror = length - k + 1
                bit = helper(n - 1, mirror)
                return '1' if bit == '0' else '0'
        return helper(n, k)
      

class Solution {
public:
    char findKthBit(int n, int k) {
        if (n == 1) return '0';
        int length = (1 << n) - 1;
        int mid = (length / 2) + 1;
        if (k == mid) return '1';
        else if (k < mid) return findKthBit(n - 1, k);
        else {
            int mirror = length - k + 1;
            char bit = findKthBit(n - 1, mirror);
            return bit == '0' ? '1' : '0';
        }
    }
};
      

class Solution {
    public char findKthBit(int n, int k) {
        if (n == 1) return '0';
        int length = (1 << n) - 1;
        int mid = (length / 2) + 1;
        if (k == mid) return '1';
        else if (k < mid) return findKthBit(n - 1, k);
        else {
            int mirror = length - k + 1;
            char bit = findKthBit(n - 1, mirror);
            return bit == '0' ? '1' : '0';
        }
    }
}
      

var findKthBit = function(n, k) {
    function helper(n, k) {
        if (n === 1) return '0';
        let length = (1 << n) - 1;
        let mid = Math.floor(length / 2) + 1;
        if (k === mid) return '1';
        else if (k < mid) return helper(n - 1, k);
        else {
            let mirror = length - k + 1;
            let bit = helper(n - 1, mirror);
            return bit === '0' ? '1' : '0';
        }
    }
    return helper(n, k);
};
      

Problem Description

Given two integers n and k, you are to find the k-th bit in the n-th binary string Sn constructed as follows:

• S1 = "0"
• For i > 1, Si = Si-1 + "1" + reverse(invert(Si-1))

Here, reverse(x) means reversing the string x, and invert(x) means inverting every bit in x (changing '0' to '1' and '1' to '0').

You are to return the k-th character (1-indexed) of Sn.

Constraints:

• 1 ≤ n ≤ 20
• 1 ≤ k ≤ 2ⁿ - 1
• There is exactly one valid answer for each input.

Thought Process

At first glance, it seems we need to build the entire binary string Sn and simply return the k-th character. However, since the length of Sn grows exponentially (for example, S20 is over a million characters long), this brute-force approach is not feasible.

Instead, we need to find a way to determine the k-th character without generating the whole string. By analyzing the recursive construction of Sn, we realize that each string is built from the previous one, a '1', and the reversed-inverted previous string. This structure is symmetric, and the position of k tells us which part of the construction it falls into.

The challenge is to map the k-th position back to a corresponding position in a smaller problem, potentially inverting the bit if it falls into the reversed-inverted part.

Solution Approach

• Recursive Structure:
  • Each Sn is built as: Sn-1 + "1" + reverse(invert(Sn-1)).
  • The length of Sn is 2^n - 1.
  • The middle character is always '1', at position mid = (length // 2) + 1.
• Recursive Algorithm:
  1. If n == 1, return '0' (base case).
  2. Compute mid as described above.
  3. If k == mid, return '1' (it's the center).
  4. If k < mid, the answer is the k-th bit of Sn-1 (left half).
  5. If k > mid, find the "mirrored" position in the left half: mirror = length - k + 1.
     • Recursively find the bit at mirror in Sn-1.
     • Invert the bit (since the right half is inverted).
• Efficiency:
  • This approach avoids building the full string, and only recurses down log(n) times.
  • Each recursion reduces the problem size by one.

Example Walkthrough

Let's consider n = 3, k = 5:

• Step 1: S1 = "0"
• Step 2: S2 = "0" + "1" + reverse(invert("0")) = "0" + "1" + "1" = "011"
• Step 3: S3 = "011" + "1" + reverse(invert("011"))
  • invert("011") = "100"
  • reverse("100") = "001"
  • So S3 = "011" + "1" + "001" = "0111001"
• Find 5th bit of S₃:
  • Length = 7, mid = 4
  • k = 5 > mid, so mirror = 7 - 5 + 1 = 3
  • Find 3rd bit in S₂ ("011"), which is '1'
  • Invert it: '1' → '0'
  • So, the answer is '0'

Time and Space Complexity

• Brute-force approach:
  • Time: O(2ⁿ) — constructing the full string.
  • Space: O(2ⁿ) — storing the full string.
• Optimized recursive approach:
  • Time: O(n) — one recursive call per level, up to n levels.
  • Space: O(n) — recursion stack depth.
  • No need to store the whole string at any point.

Summary

By exploiting the recursive structure and symmetry of the binary string construction, we can efficiently find the k-th bit without generating huge strings. The key insight is to recursively map the position back to a smaller string and invert when necessary, reducing both time and space complexity from exponential to linear in n. This makes the solution elegant, efficient, and scalable even for the largest constraints.