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
, the1st
row is0
, the2nd
row is01
, and the3rd
row 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 <= 30
-
1 <= k <= 2n - 1
SOLUTION:
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if n == 1 and k == 1:
return 0
prev = self.kthGrammar(n - 1, (k + 1) >> 1)
if k & 1:
return prev
return 1 - prev
Top comments (0)