Formatted question description: https://leetcode.ca/all/779.html
779. Kth Symbol in Grammar
Level
Medium
Description
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 1indexed.)
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:
N
will be an integer in the range[1, 30]
.K
will be an integer in the range[1, 2^(N1)]
.
Solution
Observe each row. It can be seen that row N + 1
is obtained from row N
by copying the content of row N
and then concatenating the reversed content of row N
. Row 1 is “0” and row 2 is “01”, which are quite obvious. For N >= 2
, the left half of the content in row N
and the right half of the content in row N
are reversed to each other, so the content of row N + 1
is obtained in the way mentioned above.
This problem can be solved without using N
, and only K
is needed. While K
is greater than 1, replace K
with its complement, where the complement of K
is defined as the smallest positive integer C
such that K + C = 2^M + 1
where M
is a positive integer.
Each time K
is replaced with its complement, does the symbol change? Calculate log = Math.ceil(Math.log(K) / Math.log(2))
. If log
is odd, then the symbol changes. Otherwise, the symbol remains unchanged.
After K
becomes 1, count the number of times that the symbol is changed. Since the symbol at index 1 is 0, if the symbol is changed odd number of times, return 1. Otherwise, return 0.

class Solution { public int kthGrammar(int N, int K) { int reverseCount = 0; while (K > 1) { int log = (int) Math.ceil(Math.log(K) / Math.log(2)); int power2 = (int) Math.pow(2, log); K = power2 + 1  K; if (log % 2 == 1) reverseCount++; } return reverseCount % 2; } }

// OJ: https://leetcode.com/problems/kthsymbolingrammar/ // Time: O(N) // Space: O(N) class Solution { public: int kthGrammar(int n, int k) { if (n == 1) return 0; return k <= (1 << (n  2)) ? kthGrammar(n  1, k) : (1  kthGrammar(n  1, k  (1 << (n  2)))); } };

class Solution(object): def kthGrammar(self, N, K): """ :type N: int :type K: int :rtype: int """ if K == 1: return 0 if K <= (1 << (N  2)): return self.kthGrammar(N  1, K) else: return 1  self.kthGrammar(N  1, K  (1 << (N  2)))