# LeetCode 779: K-th Symbol in Grammar

## Problem Restatement

We build a table of rows.

The first row is:

```text
0
```

To build the next row, every symbol is replaced:

| Symbol | Becomes |
|---|---|
| `0` | `01` |
| `1` | `10` |

So the first few rows are:

```text
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

| Item | Meaning |
|---|---|
| Input | Integers `n` and `k` |
| Output | The `k`-th symbol in row `n` |
| Indexing | `k` is 1-indexed |
| Row length | Row `n` has `2^(n - 1)` symbols |
| Constraints | `1 <= n <= 30` and `1 <= k <= 2^(n - 1)` |

Function shape:

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

## Examples

Example 1:

```python
n = 1
k = 1
```

Row `1` is:

```text
0
```

So the answer is:

```python
0
```

Example 2:

```python
n = 2
k = 1
```

Row `2` is:

```text
01
```

The first symbol is `0`.

So the answer is:

```python
0
```

Example 3:

```python
n = 2
k = 2
```

Row `2` is:

```text
01
```

The second symbol is `1`.

So the answer is:

```python
1
```

## First Thought: Build the Rows

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

Start with:

```python
row = "0"
```

Then repeatedly replace each symbol:

```text
0 -> 01
1 -> 10
```

After building row `n`, return:

```python
row[k - 1]
```

This works for small `n`.

## Problem With Building the Rows

The row length doubles every time.

Row `n` has:

```text
2^(n - 1)
```

symbols.

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

```text
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`.

| Parent | Left child | Right child |
|---|---|---|
| `0` | `0` | `1` |
| `1` | `1` | `0` |

So:

| Position `k` in row `n` | Relationship |
|---|---|
| Odd `k` | Same as parent |
| Even `k` | Opposite of parent |

The parent position in the previous row is:

```python
(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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each recursive call moves from row `n` to row `n - 1` |
| Space | `O(n)` | The recursion stack has depth `n` |

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

## Implementation

```python
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:

```python
if n == 1:
    return 0
```

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

```python
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:

```python
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:

```python
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`.

```python
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

```python
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:

| Test | Why |
|---|---|
| `n = 1, k = 1` | Base case |
| Row `2` | Checks both children of `0` |
| Row `3` | Checks generated pattern `0110` |
| Larger row | Checks recursive parent logic |
| `n = 30` | Checks large input without building the row |