K-th Symbol in Grammar

LeetCode 795 | Difficulty: Medium

Medium

Problem Description

We build a table of n rows (1-indexed). We start by writing 0 in the 1^st 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 `1^st` row is `0`, the `2^nd` row is `01`, and the `3^rd` row is `0110`.

Given two integer n and k, return the k^th (1-indexed) symbol in the n^th 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 <= 30`

- `1 <= k <= 2^n - 1`

Topics: Math, Bit Manipulation, Recursion

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 40 ms)

Metric	Value
Runtime	40 ms
Memory	14 MB
Date	2019-12-15

Solution

public class Solution {
    public int KthGrammar(int N, int K) {
     K--;
    int cnt = 0;
    while (K!=0)
    {
        cnt += K & 1;
        K >>= 1;
    }
    return cnt % 2;
}
}

---

Complexity Analysis

Approach	Time	Space
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Try to represent the current (N, K) in terms of some (N-1, prevK). What is prevK ?