> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/recursion/779-k-th-symbol-in-grammar.md).

# 779 K-th Symbol in Grammar

## 779. [K-th Symbol in Grammar](https://leetcode.com/problems/k-th-symbol-in-grammar/description/)

## 1. Question

On the first row, we write a`0`. Now in every subsequent row, we look at the previous row and replace each occurrence of`0`with`01`, and each occurrence of`1`with`10`.

Given row`N`and index`K`, return the`K`-th indexed symbol in row`N`. (The values of`K`are 1-indexed.) (1 indexed).

```
Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

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

**Note:**

1. `N`will be an integer in the range`[1, 30]`.
2. `K`will be an integer in the range`[1, 2^(N-1)]`.

## 2. Implementation

**(1) Recursion**

思路: 可以把这题看成是一个fully binary tree,其中node是0或者1, 如果node是0的话，它的left child是0，right child是1，node是1的话，left child是1， right child是0.要知道第N行，第K列的数是1还是0，我们要知道第N - 1行, 第 (K + 1)/2列 ((K + 1)/ 2可以得到当前node的parent node)的数是什么，根据这个再判断K的奇偶性得到结果

```java
class Solution {
    public int kthGrammar(int N, int K) {
        if (N == 1) return 0;

        int symbolInLastRow = kthGrammar(N - 1, (K + 1) / 2);

        if (symbolInLastRow == 0) {
            return K % 2 == 0 ? 1 : 0;
        }
        else {
            return K % 2 == 0 ? 0 : 1;
        }
    }
}
```

## 3. Time & Space Complexity

**Recursion:** 时间复杂度O(N), 空间复杂度O(N), 递归的深度是N