⚡Flashcard Drill➔
NeetCode #208LC-779MediumTwo Pointers
← Back to All Problems

#208 · #779 · K-th Symbol in Grammar(第 K 个语法符号)

📌 Problem Statement & Constraints

We build row 1 as 0. Row i is obtained from row i-1 by replacing each 0 with 01 and each 1 with 10. Given n and k (1-indexed), return the k-th symbol in row n. Constraints: 1 <= n <= 30, 1 <= k <= 2^(n-1).

💡 Core Algorithmic Approaches

  1. The expansion is the Thue-Morse sequence: the value at position k in row n is the parity of the number of 1 bits in k - 1.
  2. Intuition: moving from a parent position to a child position appends one bit, and each appended bit flips the value exactly when the parent index had a certain parity.
  3. So the answer is bin(k - 1).count("1") % 2 -- O(log k) time and O(1) space.
  4. A recursive alternative halves k at each level, which is the same idea expressed differently.

💻 Benchmark Python3 Implementation

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        # Thue-Morse: the symbol is the parity of the popcount of (k - 1)
        return bin(k - 1).count("1") % 2


# Recursive formulation: halve k at each level
class Solution2:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        parent = self.kthGrammar(n - 1, (k + 1) // 2)
        if k % 2 == 1:                 # first child keeps the parent's value
            return parent
        return 1 - parent              # second child flips it

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log k) for the bit-count version, or O(n) for the recursion.
💾 Space Complexity
O(1) for the bit-count version, O(n) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Generating row n explicitly: it has 2^(n-1) symbols, up to 5 * 10^8 for n = 30.
  • Forgetting the 1-indexed k: the formula uses k - 1.
  • Assuming the recursion base is k == 1: the base is n == 1, where the single symbol is 0.
  • Getting the child parity backwards: the first child (odd k) keeps the parent's value and the second child flips it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems