# K-Th Symbol In Grammar Problem

## Description

LeetCode Problem 779.

We build a table of n rows (1-indexed). We start by writing 0 in the 1^st row. 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.

• For example, for n = 3, the 1^st row is 0, the 2^nd row is 01, and the 3^rd row is 0110.

Given two integer n and k, return the k^th (1-indexed) symbol in the n^th row of a table of n rows.

Example 1:

``````1
2
3
Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0
``````

Example 2:

``````1
2
3
4
5
Input: n = 2, k = 1
Output: 0
Explanation:
row 1: 0
row 2: 01
``````

Example 3:

``````1
2
3
4
5
Input: n = 2, k = 2
Output: 1
Explanation:
row 1: 0
row 2: 01
``````

Example 4:

``````1
2
3
4
5
6
Input: n = 3, k = 1
Output: 0
Explanation:
row 1: 0
row 2: 01
row 3: 0110
``````

Constraints:

• 1 <= n <= 30
• 1 <= k <= 2^n - 1

## Sample C++ Code

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