Algorithm
Problem Name: 779. K-th Symbol in Grammar
Problem Link: https://leetcode.com/problems/k-th-symbol-in-grammar/
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int kthGrammar(int N, int K) {
return N == 1 ? 0 : kthGrammar(N - 1, (K + 1) / 2) ? K % 2 : !(K % 2);
}
};
Input
n = 1, k = 1
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const kthGrammar = function(N, 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;
};
Input
n = 1, k = 1
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def kthGrammar(self, N: int, K: int) -> int:
return N > 1 and self.kthGrammar(N - 1, (K + 1) // 2) ^ ((K -1) % 2) or 0
Input
n = 2, k = 1