Problem

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, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.

Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.

Examples

Example 1

1
2
3

Input: n = 1, k = 1
Output: 0
Explanation: row 1: _0_

Example 2

1
2
3
4
5

Input: n = 2, k = 1
Output: 0
Explanation: 
row 1: 0
row 2: _0_ 1

Example 3

1
2
3
4
5

Input: n = 2, k = 2
Output: 1
Explanation: 
row 1: 0
row 2: 0 _1_

Constraints

  • 1 <= n <= 30
  • 1 <= k <= 2n - 1

Solution

Method 1 – Recursion Based on Parent Symbol

Intuition

The k-th symbol in the n-th row depends on its parent in the previous row. Each 0 generates 01, and each 1 generates 10. The left child is always the same as the parent, the right child is the flipped parent. This leads to a recursive solution.

Approach

  1. If n == 1, return 0 (base case).
  2. Find the parent position: parent = (k+1)//2 if 1-indexed.
  3. Recursively get the parent’s value.
  4. If k is odd (left child), return parent value. If even (right child), return flipped parent value (1 - parent).

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        int parent = kthGrammar(n-1, (k+1)/2);
        if (k % 2 == 1) return parent;
        return 1 - parent;
    }
};
1
2
3
4
5
6

func kthGrammar(n int, k int) int {
    if n == 1 { return 0 }
    parent := kthGrammar(n-1, (k+1)/2)
    if k%2 == 1 { return parent }
    return 1 - parent
}
1
2
3
4
5
6
7

class Solution {
    public int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        int parent = kthGrammar(n-1, (k+1)/2);
        return k % 2 == 1 ? parent : 1 - parent;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun kthGrammar(n: Int, k: Int): Int {
        if (n == 1) return 0
        val parent = kthGrammar(n-1, (k+1)/2)
        return if (k % 2 == 1) parent else 1 - parent
    }
}
1
2
3
4
5
6

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        parent = self.kthGrammar(n-1, (k+1)//2)
        return parent if k % 2 == 1 else 1 - parent
1
2
3
4
5
6
7

impl Solution {
    pub fn kth_grammar(n: i32, k: i32) -> i32 {
        if n == 1 { return 0; }
        let parent = Solution::kth_grammar(n-1, (k+1)/2);
        if k % 2 == 1 { parent } else { 1 - parent }
    }
}
1
2
3
4
5
6
7

class Solution {
    kthGrammar(n: number, k: number): number {
        if (n === 1) return 0;
        const parent = this.kthGrammar(n-1, Math.floor((k+1)/2));
        return k % 2 === 1 ? parent : 1 - parent;
    }
}

Complexity

  • ⏰ Time complexity: O(n), as the recursion depth is n.
  • 🧺 Space complexity: O(n), due to the recursion stack.