What is the most efficient way to find the K-th symbol in the grammar sequence?

Use bit manipulation by counting 1s in the binary representation of K-1 or recursively map K to its parent in row N-1.

Why is recursion commonly used in this problem?

Recursion naturally reflects the sequence's generation pattern where each row is built from the previous row's symbols.

Can I calculate the symbol without constructing the entire row?

Yes, by tracking flips via bit counting or parent mapping, you can determine the K-th symbol directly.

What common mistakes should I avoid?

Avoid generating the full row, misapplying 1-based indexing, or forgetting flips on even positions.

How does the K-th Symbol in Grammar problem illustrate math plus bit manipulation patterns?

It uses binary representation to track symbol flips, combining math insight with bitwise operations to compute the answer efficiently.

#779

Medium

auto_awesome数学·位运算

LeetCode 题解工作台

第K个语法符号

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0 。接下来的每一行，将前一行中的 0 替换为 01 ， 1 替换为 10 。例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。给定行数 n 和序数 k ，返回第 n 行中第…

数学位运算递归

题目描述

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例 1:

输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2:

输入: n = 2, k = 1
输出: 0
解释: 
第一行: 0 
第二行: 01

示例 3:

输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

提示:

1 <= n <= 30
1 <= k <= 2^{n - 1}

lightbulb

解题思路

方法一：递归

我们先来看一下前几行的规律：

n = 1: 0
n = 2: 0 1
n = 3: 0 1 1 0
n = 4: 0 1 1 0 1 0 0 1
n = 5: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
...

可以发现，每一行的前半部分和上一行完全一致，后半部分是上一行的反转。注意，这里的“反转”指的是 $0$ 变 $1$ , $1$ 变 $0$ 。

如果 $k$ 在前半部分，那么第 $k$ 个字符就是上一行的第 $k$ 个字符，直接递归 $kthGrammar(n - 1, k)$ 即可。

如果 $k$ 在后半部分，那么第 $k$ 个字符就是上一行的第 $k - 2^{n - 2}$ 个字符的反转，即 $kthGrammar(n - 1, k - 2^{n - 2}) \oplus 1$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        if k <= (1 << (n - 2)):
            return self.kthGrammar(n - 1, k)
        return self.kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1

speed

复杂度分析

指标	值
时间	complexity is O(log k) because each step halves the position until reaching the first row. Space complexity is O(1) if using iterative bit tracking, as no full row is stored.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to notice the recursive generation of the grammar sequence quickly.
question_mark
Check if the solution avoids full row construction and leverages math or bit manipulation.
question_mark
Look for clarity in mapping K from row N to row N-1 to handle flips correctly.

warning

常见陷阱

外企场景

error
Attempting to build the entire row, which causes memory overflow for larger N.
error
Miscounting indices due to 1-based versus 0-based numbering.
error
Failing to correctly apply flips when K is an even index in the recursion path.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute multiple K-th symbols in the same row efficiently using batch bitwise operations.
arrow_right_alt
Extend the pattern to ternary or quaternary grammar sequences, adjusting the flip logic.
arrow_right_alt
Query a range of symbols in row N without generating the full sequence.

help

常见问题

外企场景

继续练习

#342 4的幂 #231 2 的幂 #782 变为棋盘