795. K-th Symbol in Grammar

• Difficulty: Medium

• Topics: Recursion

• Similar Questions:

Problem:

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)].

Solutions:

class Solution {
public:
    int kthGrammar(int N, int K) {
        --K;
        return helper(N, K);
    }

private:
    int helper(int N, int K) {
        if (N == 1) return 0; 
        int lastLevel = helper(N - 1, K/2);

        if (lastLevel == 0) return K % 2 == 0 ? 0 : 1;
        else return K % 2 == 0 ? 1 : 0;
    }
};