LeetCode 1545 - Find Kth Bit in Nth Binary String

LeetCode Problem 1545

Difficulty: 🟡 Medium
Topics: String, Recursion, Simulation

Solution

Problem Understanding

The problem defines a recursively constructed binary string sequence:

• S1 = "0"
• Si = Si-1 + "1" + reverse(invert(Si-1))

For every new level, we take the previous string, append "1", then append the reversed and bit-inverted version of the previous string.

The task is to return the kth bit in the string Sn.

To understand the construction clearly, consider how the sequence grows:

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

Each string roughly doubles in size plus one extra character. More specifically:

$$|S_n| = 2^n - 1$$

The input consists of:

• n, which determines which recursive string we are working with
• k, which specifies the 1-indexed position of the bit we need to return

The output is a single character, either "0" or "1".

The constraints are small enough that even generating the full string is technically possible:

$$1 \le n \le 20$$

The maximum length is:

$$2^{20} - 1 \approx 10^6$$

So brute force is feasible, but the problem is designed to test recognition of the recursive structure rather than simple simulation.

Several edge cases are important:

• When n = 1, the string contains only one character.
• When k points exactly to the middle character, the answer is always "1" for n > 1.
• When k lies in the mirrored second half, we must carefully reverse the index and invert the resulting bit.
• Since indexing is 1-based, off-by-one errors are common.

Approaches

Brute Force Construction

The most direct approach is to explicitly build every string from S1 up to Sn.

For each iteration:

1. Take the previous string.
2. Invert every bit.
3. Reverse the inverted string.
4. Concatenate:

• original string
• "1"
• reversed inverted string

After constructing Sn, return the character at index k - 1.

This works because it follows the exact recursive definition from the problem statement.

However, this approach repeatedly copies strings and performs reversals. While still acceptable for the given constraints, it is not the most elegant solution and uses unnecessary memory.

Recursive Observation

The key insight is that we never need to construct the entire string.

Every string has the structure:

$$S_n = S_{n-1} + "1" + reverse(invert(S_{n-1}))$$

The middle position is always:

$$mid = 2^{n-1}$$

This gives three cases:

1. If k == mid, the answer is "1".
2. If k < mid, the answer is the same as the kth bit of S(n-1).
3. If k > mid, the answer comes from the mirrored position in the reversed inverted half.

The mirrored index is:

$$mirrored = length - k + 1$$

Since the second half is inverted, we recursively compute the mirrored bit and flip it.

This reduces the problem to recursive divide-and-conquer without constructing the string.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(2^n)	Explicitly constructs the full string
Optimal	O(n)	O(n)	Uses recursive structure and mirrored indices

Algorithm Walkthrough

1. Compute the total length of Sn.

The length of Sn is:

$$2^n - 1$$

This allows us to determine the middle position. 2. Find the middle index.

The middle character is always at:

$$mid = \frac{length + 1}{2}$$

This position always contains "1". 3. Check whether k is the middle position.

If k == mid, immediately return "1". 4. Handle the left half.

If k < mid, the requested bit lies entirely inside S(n-1).

Therefore:

$$findKthBit(n, k) = findKthBit(n-1, k)$$ 5. Handle the right half.

If k > mid, the bit belongs to:

$$reverse(invert(S_{n-1}))$$

Because the string is reversed, we map the index back into the original left half.

The mirrored position is:

$$mirrored = length - k + 1$$ 6. Recursively compute the mirrored bit.

The right half is inverted, so after computing the mirrored bit we flip it:

• "0" becomes "1"
• "1" becomes "0"

7. Continue recursion until reaching the base case.

The smallest string is:

$$S_1 = "0"$$

So when n == 1, return "0".

Why it works

The recursive structure of Sn guarantees that every position belongs to either:

• the left copy of S(n-1)
• the middle "1"
• the reversed inverted copy of S(n-1)

The mirrored index transformation correctly maps positions from the reversed second half back into the original first half. Since the second half is also inverted, flipping the recursively computed bit produces the correct answer.

Python Solution

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

        length = (1 << n) - 1
        mid = (length + 1) // 2

        if k == mid:
            return "1"

        if k < mid:
            return self.findKthBit(n - 1, k)

        mirrored_index = length - k + 1
        bit = self.findKthBit(n - 1, mirrored_index)

        return "1" if bit == "0" else "0"

The implementation directly follows the recursive observations from the algorithm discussion.

The base case handles S1, which contains only "0".

The expression:

(1 << n) - 1

computes the length efficiently using bit shifting.

The middle position is determined so we can separate the string into its three structural regions.

If k lies in the left half, recursion continues unchanged.

If k lies in the right half, the code computes the mirrored index:

mirrored_index = length - k + 1

This maps the reversed section back into the original left half. After recursively finding the mirrored bit, the code inverts it before returning.

Because each recursive call decreases n by one, recursion depth is at most 20.

Go Solution

func findKthBit(n int, k int) byte {
	if n == 1 {
		return '0'
	}

	length := (1 << n) - 1
	mid := (length + 1) / 2

	if k == mid {
		return '1'
	}

	if k < mid {
		return findKthBit(n-1, k)
	}

	mirroredIndex := length - k + 1
	bit := findKthBit(n-1, mirroredIndex)

	if bit == '0' {
		return '1'
	}

	return '0'
}

The Go implementation mirrors the Python logic almost exactly.

The main difference is that Go returns a byte rather than a string character. Therefore, the function uses character literals like '0' and '1'.

Bit shifting works naturally with integers in Go:

(1 << n) - 1

Since n <= 20, integer overflow is never a concern.

Worked Examples

Example 1

Input:

n = 3, k = 1

We know:

S3 = "0111001"

But the recursive algorithm proceeds without constructing it.

Step	n	k	length	mid	Action
1	3	1	7	4	k < mid, recurse left
2	2	1	3	2	k < mid, recurse left
3	1	1	1	1	base case, return "0"

Final answer:

"0"

Example 2

Input:

n = 4, k = 11

Step	n	k	length	mid	Action
1	4	11	15	8	k > mid
2	4	5	15	8	mirrored index = 15 - 11 + 1 = 5
3	3	5	7	4	k > mid
4	3	3	7	4	mirrored index = 7 - 5 + 1 = 3
5	2	2	3	2	k == mid, return "1"
6	3	5	7	4	invert "1" -> "0"
7	4	11	15	8	invert "0" -> "1"

Final answer:

"1"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each recursive call reduces n by 1
Space	O(n)	Recursive call stack depth is at most n

The algorithm performs only one recursive call per level. Since n decreases by one each time, the recursion depth is at most 20.

No strings are constructed, so memory usage remains minimal aside from the recursion stack.

Test Cases

solution = Solution()

# Provided examples
assert solution.findKthBit(3, 1) == "0"  # first bit of S3
assert solution.findKthBit(4, 11) == "1"  # example from statement

# Base case
assert solution.findKthBit(1, 1) == "0"  # smallest possible input

# Middle positions are always 1
assert solution.findKthBit(2, 2) == "1"  # middle of S2
assert solution.findKthBit(3, 4) == "1"  # middle of S3
assert solution.findKthBit(4, 8) == "1"  # middle of S4

# Right-half inversion behavior
assert solution.findKthBit(2, 3) == "1"  # mirrored inverted bit
assert solution.findKthBit(3, 5) == "0"  # mirrored inverted bit

# Boundary positions
assert solution.findKthBit(4, 1) == "0"  # first bit
assert solution.findKthBit(4, 15) == "1"  # last bit

# Larger recursive depth
assert solution.findKthBit(5, 16) == "1"  # middle of S5
assert solution.findKthBit(5, 31) == "1"  # final bit

# Stress-style cases near upper limits
assert solution.findKthBit(20, 1) == "0"  # deep recursion, first bit
assert solution.findKthBit(20, (1 << 19)) == "1"  # exact middle

Test	Why
n=3, k=1	Verifies left-side recursion
n=4, k=11	Verifies mirrored inversion logic
n=1, k=1	Validates base case
Middle position tests	Confirms invariant that middle bit is always "1"
Right-half tests	Ensures inversion and mirroring are correct
Boundary position tests	Checks first and last characters
Large depth tests	Confirms recursion handles maximum constraints

Edge Cases

One important edge case occurs when n = 1. In this situation, the entire recursive structure disappears because the string is simply "0". Recursive implementations can accidentally recurse below n = 1 if the base case is not handled correctly. The implementation explicitly checks for n == 1 first and immediately returns "0".

Another important case occurs when k equals the exact middle position. Every generated string has a single central "1" inserted during construction. If this case is not handled before recursion, the algorithm may incorrectly recurse into one of the halves and produce the wrong answer. The implementation computes the middle index and returns "1" immediately when k == mid.

A third subtle edge case happens when k lies in the reversed second half. Because this region is both reversed and inverted, implementations frequently make off-by-one mistakes when computing the mirrored index. The formula:

$$mirrored = length - k + 1$$

correctly maps positions from the right half back into the left half using 1-based indexing. After recursion, the bit is inverted exactly once, which preserves correctness.

A final edge case involves very large n, such as n = 20. Constructing the full string is still technically feasible, but recursive solutions must ensure that recursion depth remains manageable. Since the algorithm makes only one recursive call per level, the maximum recursion depth is only 20, which is completely safe in both Python and Go.