Code Implementation

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        parent = self.kthGrammar(n - 1, (k + 1) // 2)
        if k % 2 == 1:
            return parent
        else:
            return 1 - parent
      

class Solution {
public:
    int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        int parent = kthGrammar(n - 1, (k + 1) / 2);
        if (k % 2 == 1)
            return parent;
        else
            return 1 - parent;
    }
};
      

class Solution {
    public int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        int parent = kthGrammar(n - 1, (k + 1) / 2);
        if (k % 2 == 1)
            return parent;
        else
            return 1 - parent;
    }
}
      

var kthGrammar = function(n, k) {
    if (n === 1) return 0;
    const parent = kthGrammar(n - 1, Math.floor((k + 1) / 2));
    if (k % 2 === 1)
        return parent;
    else
        return 1 - parent;
};
      

Problem Description

The K-th Symbol in Grammar problem asks: Given two integers, n and k, return the k-th symbol in the n-th row of a special grammar sequence.

• The sequence starts with row 1: 0.
• Each subsequent row is generated by replacing every 0 in the previous row with 01, and every 1 with 10.
• Given n (the row number, 1-indexed) and k (the position in that row, 1-indexed), return the value (either 0 or 1).
• Constraints: 1 <= n <= 30, 1 <= k <= 2^{n-1}

Thought Process

At first glance, the problem seems to suggest generating the entire string up to row n and then simply indexing the k-th character. However, as n increases, the length of the row doubles each time, making this approach impractical for large n. For example, row 30 would have over 500 million characters!

Instead, we need to find a way to determine the k-th symbol without constructing the full row. Observing the recursive pattern of the grammar, we notice that each symbol in a row is determined by its "parent" symbol in the previous row and whether it is a left or right child (odd or even position). This insight leads us to a recursive solution that works efficiently.

Solution Approach

Let's break down the recursive relationship:

• Row 1: 0
• To generate the next row, replace every 0 with 01 and every 1 with 10.
• For any position k in row n, its "parent" is at position (k+1)//2 in row n-1.
• If k is odd, the symbol is the same as its parent. If k is even, it's the complement (i.e., 1 - parent).

Step-by-step algorithm:

1. If n == 1, return 0 (base case).
2. Find the parent symbol using recursion: parent = kthGrammar(n-1, (k+1)//2).
3. If k is odd, return parent. If k is even, return 1 - parent.

This approach avoids building full strings and instead computes the answer in O(n) time and O(n) stack space.

Example Walkthrough

Let's walk through an example with n = 4 and k = 5:

• Row 1: 0
• Row 2: 01
• Row 3: 0110
• Row 4: 01101001

The 5th symbol in row 4 is 1.

1. Call kthGrammar(4, 5)
2. Parent is at (5+1)//2 = 3: kthGrammar(3, 3)
3. Parent is at (3+1)//2 = 2: kthGrammar(2, 2)
4. Parent is at (2+1)//2 = 1: kthGrammar(1, 1) returns 0
5. k = 2 is even, so return 1 - 0 = 1
6. k = 3 is odd, so return 1
7. k = 5 is odd, so return 1

Thus, the answer is 1.

Time and Space Complexity

Brute-force approach:

• Time: O(2^n) — Generating the entire row of length 2^{n-1}.
• Space: O(2^n) — Storing the full row.

• Time: O(n) — One recursive call per level.
• Space: O(n) — Due to the recursion stack.

This is a huge improvement and allows us to solve the problem efficiently for all allowed values of n.

Summary

The key insight is recognizing the recursive nature of the grammar sequence. Each symbol is determined by its parent in the previous row and whether it occupies an odd or even position. By using recursion and avoiding full string construction, we achieve a solution that is both elegant and highly efficient.