---
tags: data_structure_python
---

# K-th Symbol in Grammar <img src="https://img.shields.io/badge/-easy-brightgreen">

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

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^(N-1)].

# Solution


### Solution 1: Recursive 1

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        if N == 1:
            return "0"
        else:
            row = self.kthGrammar(N-1, (K+1)//2)
            if row == "0":
                return "0" if (K%2)-1 == 0 else "1"
            else:
                return "1" if (K%2)-1 == 0 else "0"

### Solution 2: Recursive 2

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        
        if N == 1:
            # Base case:
            return 0
        
        else:
            # General case:
            if K % 2 == 0:
                # even index of current level is opposite of parent level's [(K+1)//2]
                return 0 if self.kthGrammar(N-1, (K+1)//2) else 1
            else:
                # odd index of current level is the same as parent level's [(K+1)//2]
                return 1 if self.kthGrammar(N-1, (K+1)//2) else 0