Find Kth Bit in Nth Binary String

LeetCode 1545, Find Kth Bit in Nth Binary String, gives you a recursively defined sequence of binary strings. Starting from S1 = "0", each subsequent string is built by taking the previous one, appending a "1", then appending the reversed and inverted copy of the previous string. Given n and k, you need to return the kth bit (1-indexed) of Sn.

The catch is that these strings grow exponentially. Sn has length 2^n - 1, so S20 has over a million characters. Building the whole string just to read one bit would be wasteful. Fortunately, the recursive structure gives you a shortcut.

The recursive structure

Every string Sn (for n > 1) has three parts:

1. First half: a copy of S(n-1), occupying positions 1 through 2^(n-1) - 1
2. Middle bit: always "1", at position 2^(n-1)
3. Second half: the reverse of the inverted S(n-1), occupying positions 2^(n-1) + 1 through 2^n - 1

This means you can figure out any single bit without constructing the string. You just need to determine which region your target position k falls into.

The algorithm

Here is the plan:

1. Compute the length of Sn: len = 2^n - 1. The middle position is mid = 2^(n-1).
2. If k == mid, the answer is "1" (the middle bit is always 1).
3. If k < mid, the bit is in the first half. This is just S(n-1), so recurse with n-1 and the same k.
4. If k > mid, the bit is in the second half. The second half is the reverse of the inverted S(n-1). Mirror k to its corresponding position in S(n-1): k' = len - k + 1. Recurse with n-1 and k', then flip the result.

Base case: when n == 1, the string is "0", so return "0".

Each recursive call reduces n by 1, so you make at most n calls. No string construction needed.

The code

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

    length = (1 << n) - 1
    mid = 1 << (n - 1)

    if k == mid:
        return "1"
    elif k < mid:
        return findKthBit(n - 1, k)
    else:
        # Mirror position and flip the result
        mirror_k = length - k + 1
        result = findKthBit(n - 1, mirror_k)
        return "0" if result == "1" else "1"

Walk through what happens:

1. Base case: If n == 1, the string is just "0". Return it.
2. Compute the structure: length is 2^n - 1 (using bit shift for speed). mid is 2^(n-1).
3. Hit the middle: If k equals mid, the bit is always "1".
4. First half: If k < mid, the bit lives in S(n-1) at the same position. Recurse without any transformation.
5. Second half: If k > mid, compute the mirrored position mirror_k = length - k + 1. This is where the bit came from in S(n-1) before the reverse-and-invert operation. Recurse to find that bit, then flip it (because of the inversion).

Visual walkthrough

Here is a trace of finding bit 11 in S4. At each level of recursion, you determine which region k falls into and either recurse directly or mirror and flip.

The recursion goes four levels deep. Each level either passes k through unchanged (first half) or mirrors it and marks a flip (second half). At the bottom you hit the base case, then unwind the flips.

Complexity analysis

You make at most n recursive calls, each doing O(1) work. The recursion depth is n, so the stack space is O(n). Since the problem constraints limit n to 20, both time and space are trivially small.

Compare this to the brute force approach of building the entire string, which would take O(2^n) time and space. For n=20, that is over a million characters. The recursive approach is exponentially faster.

Iterative version

You can also solve this iteratively by tracking the number of flips as you walk down the levels:

def findKthBit(n: int, k: int) -> str:
    flips = 0

    while n > 1:
        length = (1 << n) - 1
        mid = 1 << (n - 1)

        if k == mid:
            return "1" if flips % 2 == 0 else "0"
        elif k > mid:
            k = length - k + 1
            flips += 1

        n -= 1

    # n == 1, base bit is "0"
    return "0" if flips % 2 == 0 else "1"

This eliminates the recursion stack, bringing space down to O(1). The logic is the same: at each level, check if k is at the middle, in the first half, or in the second half. If it is in the second half, mirror and count a flip. Either way, reduce n by 1.

Building blocks

This problem combines two reusable techniques.

Recursive string navigation

Instead of constructing a recursively defined string, you navigate its structure. At each level, you figure out which piece your target falls into and recurse into that piece. This same idea applies to problems where a string or sequence is defined by a recurrence and you need to answer queries about specific positions.

Mirror and flip

The second half of each string is the reverse-inverse of the first half. When your target lands in the second half, you mirror the position (because of the reversal) and flip the result (because of the inversion). This transform-and-recurse pattern shows up whenever a problem has symmetry you can exploit to reduce the search space.

Edge cases

k hits the middle at some level. The middle bit is always "1". If k equals 2^(n-1) at any recursion level, you can return immediately (after applying any accumulated flips).

k = 1 for any n. The first bit of every Sn is always "0", because S1 starts with "0" and every subsequent string copies S(n-1) at the front. The recursion handles this naturally by always landing in the first-half case until reaching the base case.

n = 1. The string is just "0", and k must be 1. The base case returns "0" directly.

Large n with k deep in the second half. Each second-half hit adds one flip. The total number of flips determines whether you return the base bit or its complement. Even if every level mirrors, you only do n steps.

From understanding to recall

The key insight here is small: the length is 2^n - 1, the middle is 2^(n-1), and second-half positions mirror with a flip. But under interview pressure, you might hesitate on the mirror formula (length - k + 1) or forget whether to flip on first-half or second-half hits. These are the details that slip.

Spaced repetition locks them in. You drill the three-way branch (middle, first half, second half) as one brick and the mirror-and-flip transform as another. After a few reps at increasing intervals, the recursion template is automatic. When you see a problem with recursive structure and positional queries, you already know the shape of the solution.

Related posts

• Decode String - Another medium string problem that uses recursion to navigate nested structure
• Count and Say - A sequence-building problem where each term is defined by the previous one
• Binary Search - The classic divide and conquer pattern of halving the search space at each step