Welcome to Subscribe On Youtube
779. K-th Symbol in Grammar
Description
We build a table of n rows (1-indexed). We start by writing 0 in the 1st 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, the1strow is0, the2ndrow is01, and the3rdrow is0110.
Given two integer n and k, return the kth (1-indexed) symbol in the nth 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 <= 301 <= k <= 2n - 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(k-1)) & 1 } -
function kthGrammar(n: number, k: number): number { if (n == 1) { return 0; } if (k <= 1 << (n - 2)) { return kthGrammar(n - 1, k); } return kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1; }