779 K-th Symbol in Grammar

# 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).
1
Examples:
2
Input: N = 1, K = 1
3
Output: 0
4
5
Input: N = 2, K = 1
6
Output: 0
7
8
Input: N = 2, K = 2
9
Output: 1
10
11
Input: N = 4, K = 5
12
Output: 1
13
14
Explanation:
15
row 1: 0
16
row 2: 01
17
row 3: 0110
18
row 4: 01101001
Copied!
Note:
1. 1.
`N`will be an integer in the range`[1, 30]`.
2. 2.
`K`will be an integer in the range`[1, 2^(N-1)]`.

# 2. Implementation

(1) Recursion

1
class Solution {
2
public int kthGrammar(int N, int K) {
3
if (N == 1) return 0;
4
5
int symbolInLastRow = kthGrammar(N - 1, (K + 1) / 2);
6
7
if (symbolInLastRow == 0) {
8
return K % 2 == 0 ? 1 : 0;
9
}
10
else {
11
return K % 2 == 0 ? 0 : 1;
12
}
13
}
14
}
Copied!

# 3. Time & Space Complexity

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