Problem 12.5 · RecursionMedium

K-th Symbol in Grammar

What it teaches: Recurse on the structure instead of building it: each symbol depends only on its parent in the previous row.

Practise it on judges as “K-th Symbol in Grammar”.

The problem

Row 1 is "0". Each next row replaces every 0 with "01" and every 1 with "10". Given n and k (1-indexed), return the k-th symbol of row n.

Example 1

Input: n = 1, k = 1
Output: 0

Example 2

Input: n = 2, k = 2
Output: 1

Row 2 is "01".

Example 3

Input: n = 3, k = 3
Output: 1

Row 3 is "0110".

Constraints

1 ≤ n ≤ 30
1 ≤ k ≤ 2ⁿ⁻¹

Pattern clues in the wording

→ Row n has 2ⁿ⁻¹ symbols: too big to build
→ Each symbol comes from one parent

These clues point to Recursion: Solve the problem by solving a smaller version of it, with a base case that stops the calls.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int kthGrammar(int n, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 1 k = 1	0
2	n = 2 k = 2	1
3	n = 3 k = 3	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: recurse on the parent · O(n)

Optimal: recurse on the parent

Time O(n) Space O(n) stack

If n == 1 return 0. parent = kthGrammar(n − 1, (k + 1) / 2). Return parent if k is odd, else 1 − parent.

Approach 1

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

Verdict: Thirty calls instead of building half a billion characters.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 1 (always 0)
Last symbol of a row

Mistakes people make

Building the rows as strings (memory explodes).

Interview

Follow-up questions

Is there a closed form?

Command Palette

The problem

Approaches

Optimal: recurse on the parent

Edge cases and common mistakes

Follow-up questions