Welcome to Subscribe On Youtube
779. Kth Symbol in Grammar
Description
We build a table of n
rows (1indexed). 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
, the1^{st}
row is0
, the2^{nd}
row is01
, and the3^{rd}
row is0110
.
Given two integer n
and k
, return the k^{th}
(1indexed) symbol in the n^{th}
row of a table of n
rows.
Example 1:
Input: n = 1, k = 1 Output: 0 Explanation: row 1: 0
Example 2:
Input: n = 2, k = 1 Output: 0 Explanation: row 1: 0 row 2: 01
Example 3:
Input: n = 2, k = 2 Output: 1 Explanation: row 1: 0 row 2: 01
Constraints:
1 <= n <= 30
1 <= k <= 2^{n  1}
Solutions

class Solution { public int kthGrammar(int n, int k) { return Integer.bitCount(k  1) & 1; } }

class Solution { public: int kthGrammar(int n, int k) { return __builtin_popcount(k  1) & 1; } };

class Solution: def kthGrammar(self, n: int, k: int) > int: return (k  1).bit_count() & 1

func kthGrammar(n int, k int) int { return bits.OnesCount(uint(k1)) & 1 }