#1545

Medium

LeetCode Problem Workspace

Find Kth Bit in Nth Binary String

Determine the k-th bit in the n-th binary string using a recursive construction that inverts and reverses previous strings.

string recursion simulation

Problem Statement

Given two positive integers n and k, the binary string S_n is defined recursively: S_1 = "0" and for n > 1, S_n = S_{n-1} + "1" + reverse(invert(S_{n-1})). Here, reverse(x) flips the order of characters in x, and invert(x) changes 0 to 1 and 1 to 0. You are asked to determine the k-th bit (1-indexed) of S_n without explicitly constructing the entire string.

For example, the first four strings in this sequence are S_1 = "0", S_2 = "011", S_3 = "0111001", and S_4 = "011100110110001". Given n and k within the constraints 1 <= n <= 20 and 1 <= k <= 2^n - 1, return the exact character ('0' or '1') at position k in S_n.

Examples

Example 1

Input: n = 3, k = 1

Output: "0"

S3 is "0111001". The 1st bit is "0".

Example 2

Input: n = 4, k = 11

Output: "1"

S4 is "011100110110001". The 11th bit is "1".

Constraints

1 <= n <= 20
1 <= k <= 2n - 1

Solution Approach

Recursive Index Mapping

Observe that S_n is formed as S_{n-1} + '1' + reverse(invert(S_{n-1})). If k equals the middle index, return '1'. If k is less than the middle, recursively query S_{n-1}. If k is greater, map k to the mirrored position in S_{n-1} and invert the bit.

Avoid Full String Construction

Instead of building S_n entirely, calculate the middle index as 2^{n-1}. Use recursion to trace k back to S_1. This prevents memory overhead and ensures O(n) time, which is efficient since n <= 20.

Base Case Handling

For n = 1, the string is '0', so return '0' if k = 1. All recursive calls eventually reduce to this base case, guaranteeing correctness and termination while following the exact string plus recursion pattern.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

Time complexity is O(n) because each recursive call reduces n by 1. Space complexity is O(n) due to the recursion stack. No full string is constructed, preventing exponential growth.

What Interviewers Usually Probe

Notice how recursion mirrors both reversing and inverting previous strings.
Check if candidates attempt full string construction versus index mapping.
Ask why the middle index is special and how it simplifies recursion.

Common Pitfalls or Variants

Common pitfalls

Attempting to construct the entire S_n, leading to exponential memory use.
Miscomputing the mirrored index for k > middle, causing wrong bit retrieval.
Forgetting to invert the bit after mapping k to the mirrored position.

Follow-up variants

Return a substring from position l to r in S_n using the same recursive mapping.
Count the number of '1's in S_n up to position k without full construction.
Modify the middle bit from '1' to '0' and analyze the new recursive pattern.

FAQ

What is the main trick to efficiently find the k-th bit in the n-th binary string?

The trick is using recursive index mapping with the middle bit as a pivot and mirroring k for the inverted reversed portion, avoiding full string construction.

Can this approach handle n = 20 without memory issues?

Yes, because it only uses recursion with O(n) stack space and does not store the full string, preventing exponential memory usage.

How do I determine the mirrored index when k is in the second half of S_n?

Calculate mirrored_k = length_of_Sn_minus1 - (k - middle_index - 1), then recursively find the bit at mirrored_k and invert it.

Why is the middle bit always '1' in S_n?

By definition, each S_n is S_{n-1} + '1' + reverse(invert(S_{n-1})), so the central bit separates the two halves and is always '1'.

Does this problem always use string plus recursion pattern?

Yes, the exact pattern relies on recursively building strings with concatenation, inversion, and reversal, making string plus recursion essential.

terminal

Solution

Solution 1: Case Analysis + Recursion

We can observe that for $S_n$, the first half is the same as $S_{n-1}$, and the second half is the reverse and negation of $S_{n-1}$. Therefore, we can design a function $dfs(n, k)$, which represents the $k$-th character of the $n$-th string. The answer is $dfs(n, k)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def dfs(n: int, k: int) -> int:
            if k == 1:
                return 0
            if (k & (k - 1)) == 0:
                return 1
            m = 1 << n
            if k * 2 < m - 1:
                return dfs(n - 1, k)
            return dfs(n - 1, m - k) ^ 1

        return str(dfs(n, k))

Continue Practicing

#1404 number of steps to reduce a number in binary representation to one #1324 print words vertically #1823 find the winner of the circular game