779 K-th Symbol in Grammar

779. K-th Symbol in Grammar

1. Question

On the first row, we write a0. Now in every subsequent row, we look at the previous row and replace each occurrence of0with01, and each occurrence of1with10.

Given rowNand indexK, return theK-th indexed symbol in rowN. (The values ofKare 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. Nwill be an integer in the range[1, 30].

2. Kwill 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的奇偶性得到结果

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