#779

Medium

LeetCode Problem Workspace

K-th Symbol in Grammar

Determine the K-th symbol in a recursively generated grammar table using math and bit manipulation patterns efficiently.

math bit manipulation recursion

Problem Statement

We define a binary grammar sequence starting with row 1 as '0'. Each subsequent row is generated by replacing every 0 with 01 and every 1 with 10 from the previous row. Given integers n and k, your task is to find the k-th symbol in the n-th row of this sequence without constructing the entire row.

For example, row 1 is 0, row 2 is 01, row 3 is 0110, and so on. Given n = 4 and k = 5, you need to compute the value at that position efficiently using the recursive and bit manipulation pattern, staying within the constraints 1 <= n <= 30 and 1 <= k <= 2^(n-1).

Examples

Example 1

Input: n = 1, k = 1

Output: 0

row 1: 0

Example 2

Input: n = 2, k = 1

Output: 0

row 1: 0 row 2: 01

Example 3

Input: n = 2, k = 2

Output: 1

row 1: 0 row 2: 01

Constraints

1 <= n <= 30
1 <= k <= 2n - 1

Solution Approach

Recursive Mapping Approach

Track the K-th symbol by mapping it to the parent position in row N-1. If K is even, it corresponds to the flipped value of the previous row's K/2 symbol; if K is odd, it is the same as the (K+1)/2 symbol. Apply recursion until reaching row 1.

Bit Manipulation Shortcut

Count the number of 1s in the binary representation of K-1. If this count is even, the symbol is 0; if odd, it is 1. This leverages the fact that each flip corresponds to a 1 in the path from root to position, allowing O(log k) time with O(1) space.

Iterative Parent Tracking

Start from row N and iteratively move to the corresponding parent in row N-1 using division and modulo operations. Track flips along the path to determine the final symbol without recursion, maintaining constant space.

Complexity Analysis

Metric	Value
Time	O(\log k)
Space	O(1)

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Recursion

Let's first observe the pattern of the first few rows:

1

2

3

4

5

6

7

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

Solution 2: Bit Manipulation + Brain Teaser

In the problem, the index starts from $1$. We will change $k$ to $k-1$, converting the index to start from $0$. In the following discussion, all indices start from $0$.

1

2

3

4

5

6

7

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

Continue Practicing

#342 power of four #231 power of two #782 transform to chessboard