LeetCode 779: K-th Symbol in Grammar

Problem Restatement

We build a table of rows.

The first row is:

0

To build the next row, every symbol is replaced:

So the first few rows are:

row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

Given integers n and k, return the k-th symbol in row n.

The position k is 1-indexed.

Input and Output

Function shape:

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        ...

Examples

Example 1:

n = 1
k = 1

Row 1 is:

0

So the answer is:

0

Example 2:

n = 2
k = 1

Row 2 is:

01

The first symbol is 0.

So the answer is:

0

Example 3:

n = 2
k = 2

Row 2 is:

01

The second symbol is 1.

So the answer is:

1

First Thought: Build the Rows

A direct solution is to build each row as a string.

Start with:

row = "0"

Then repeatedly replace each symbol:

0 -> 01
1 -> 10

After building row n, return:

row[k - 1]

This works for small n.

Problem With Building the Rows

The row length doubles every time.

Row n has:

2^(n - 1)

symbols.

Since n can be 30, the last row may have:

2^29

symbols.

That is more than five hundred million characters. Building the row is too expensive in memory and time.

We need to find the symbol directly.

Key Insight

Each symbol in row n - 1 creates two symbols in row n.

So:

The parent position in the previous row is:

(k + 1) // 2

So we can reduce the problem from row n to row n - 1.

If k is odd, the answer is the same as the parent.

If k is even, the answer is the inverse of the parent.

Algorithm

Use recursion.

Base case:

n == 1

The first row is always 0, so return 0.

Recursive step:

1. Find the parent symbol in row n - 1.
2. If k is odd, return the parent symbol.
3. If k is even, return the opposite symbol.

The parent index is:

parent_k = (k + 1) // 2

Correctness

We prove that the algorithm returns the k-th symbol in row n.

For the base case, row 1 contains only one symbol, 0. Therefore, when n == 1, returning 0 is correct.

Now assume we want the k-th symbol in row n, where n > 1.

Every symbol in row n is created from exactly one symbol in row n - 1. The parent position is (k + 1) // 2.

If k is odd, then the symbol is the left child of its parent. The replacement rules show that the left child is always the same as the parent: 0 creates left child 0, and 1 creates left child 1.

If k is even, then the symbol is the right child of its parent. The replacement rules show that the right child is always the opposite of the parent: 0 creates right child 1, and 1 creates right child 0.

By recursively computing the correct parent symbol, then applying the correct odd or even rule, the algorithm returns the correct symbol at position k in row n.

Complexity

Since n <= 30, this recursion depth is small.

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

        return 1 - parent

Code Explanation

The base case handles the first row:

if n == 1:
    return 0

The parent of position k is in row n - 1:

parent = self.kthGrammar(n - 1, (k + 1) // 2)

If k is odd, we are looking at the left child.

The left child is the same as its parent:

if k % 2 == 1:
    return parent

If k is even, we are looking at the right child.

The right child is the opposite of its parent:

return 1 - parent

Alternative: Count Bits

There is also a compact mathematical view.

The answer is the parity of the number of 1 bits in k - 1.

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        return (k - 1).bit_count() % 2

Why this works: moving from the root to position k can be described by the binary representation of k - 1. Each 1 means we take a right edge, which flips the value. The final symbol is 1 exactly when the number of flips is odd.

This solution does not really need n, except that n guarantees k is inside the row.

Testing

def run_tests():
    s = Solution()

    assert s.kthGrammar(1, 1) == 0

    assert s.kthGrammar(2, 1) == 0
    assert s.kthGrammar(2, 2) == 1

    assert s.kthGrammar(3, 1) == 0
    assert s.kthGrammar(3, 2) == 1
    assert s.kthGrammar(3, 3) == 1
    assert s.kthGrammar(3, 4) == 0

    assert s.kthGrammar(4, 5) == 1
    assert s.kthGrammar(4, 8) == 1

    assert s.kthGrammar(30, 1) == 0

    print("all tests passed")

run_tests()

Test coverage: