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.

#1545

Medium

auto_awesomestring·结合·递归

LeetCode 题解工作台

找出第 N 个二进制字符串中的第 K 位

给你两个正整数 n 和 k ，二进制字符串 S n 的形成规则如下： S 1 = "0" 当 i > 1 时， S i = S i-1 + "1" + reverse(invert(S i-1 )) 其中 + 表示串联操作， reverse(x) 返回反转 x 后得到的字符串，而 invert(x)…

字符串递归模拟

题目描述

给你两个正整数 n 和 k，二进制字符串 S_n 的形成规则如下：

S₁ = "0"
当 i > 1 时，S_i = S_i-1 + "1" + reverse(invert(S_i-1))

其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。

例如，符合上述描述的序列的前 4 个字符串依次是：

S₁= "0"
S₂= "011"
S₃= "0111001"
S₄ = "011100110110001"

请你返回 S_n 的 第 k 位字符 ，题目数据保证 k 一定在 S_n 长度范围以内。

示例 1：

输入：n = 3, k = 1
输出："0"
解释：S₃ 为 "0111001"，其第 1 位为 "0" 。

示例 2：

输入：n = 4, k = 11
输出："1"
解释：S₄ 为 "011100110110001"，其第 11 位为 "1" 。

示例 3：

输入：n = 1, k = 1
输出："0"

示例 4：

输入：n = 2, k = 3
输出："1"

提示：

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

lightbulb

解题思路

方法一：分类讨论 + 递归

我们可以发现，对于 $S_n$ ，其前半部分和 $S_{n-1}$ 是一样的，而后半部分是 $S_{n-1}$ 的反转取反。因此我们可以设计一个函数 $dfs(n, k)$ ，表示第 $n$ 个字符串的第 $k$ 位字符。答案即为 $dfs(n, k)$ 。

函数 $dfs(n, k)$ 的计算过程如下：

如果 $k = 1$ ，那么答案为 $0$ ；
如果 $k$ 是 $2$ 的幂次方，那么答案为 $1$ ；
如果 $k \times 2 \lt 2^n - 1$ ，说明 $k$ 在前半部分，答案为 $dfs(n - 1, k)$ ；
否则，答案为 $dfs(n - 1, 2^n - k) \oplus 1$ ，其中 $\oplus$ 表示异或运算。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为题目给定的 $n$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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))

speed

复杂度分析

指标	值
时间	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.
空间	O(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1404 将二进制表示减到 1 的步骤数 #1324 竖直打印单词 #1823 找出游戏的获胜者