# 779. K-th Symbol in Grammar

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

``````              0
/             \
0               1
/     \         /     \
0       1       1       0
/ \     / \     / \     / \
0   1   1   0   1   0   0   1
``````

``````class Solution {
public:
int kthGrammar(int N, int K) {
if (N == 1) return 0;
if (K % 2 == 0) return (kthGrammar(N - 1, K / 2) == 0) ? 1 : 0;
else return (kthGrammar(N - 1, (K + 1) / 2) == 0) ? 0 : 1;
}
};
``````

0 -> 01

1 -> 10

``````class Solution {
public:
int kthGrammar(int N, int K) {
if (N == 1) return 0;
return (~K & 1) ^ kthGrammar(N - 1, (K + 1) / 2);
}
};
``````

``````class Solution {
public:
int kthGrammar(int N, int K) {
int cnt = 0;
--K;
while (K) {
cnt += K & 1;
K >>= 1;
}
return cnt % 2;
}
};
``````

``````class Solution {
public:
int kthGrammar(int N, int K) {
int res = 0;
while (K > 1) {
K = (K % 2 == 1) ? K + 1 : K / 2;
res ^= 1;
}
return res;
}
};
``````

``````class Solution {
public:
int kthGrammar(int N, int K) {
return bitset<32>(K - 1).count() % 2;
}
};
``````

https://leetcode.com/problems/k-th-symbol-in-grammar/solution/

https://leetcode.com/problems/k-th-symbol-in-grammar/discuss/113705/JAVA-one-line

https://leetcode.com/problems/k-th-symbol-in-grammar/discuss/113697/My-3-lines-C++-recursive-solution

https://leetcode.com/problems/k-th-symbol-in-grammar/discuss/121544/C++JavaPython-Another-Solution-with-Explanation

https://leetcode.com/problems/k-th-symbol-in-grammar/discuss/113721/C++-with-explanation-three-solutions-O(n)-O(logn)-and-O(loglogn)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation