# # 【LeetCode】779. K-th Symbol in Grammar 解题报告（Python）

## # 题目描述：

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 1-indexed.) (1 indexed).

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:

1. N will be an integer in the range [1, 30].
2. K will be an integer in the range [1, 2^(N-1)].

## # 解题方法

row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001
row 5: 0110100110010110

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)))

## # 日期

2018 年 9 月 26 日 —— 美好的一周又快要过去了。。