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
- The expansion is the Thue-Morse sequence: the value at position
kin rownis the parity of the number of1bits ink - 1. - 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.
- So the answer is
bin(k - 1).count("1") % 2-- O(log k) time and O(1) space. - A recursive alternative halves
kat 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
nexplicitly: it has2^(n-1)symbols, up to 5 * 10^8 for n = 30. - Forgetting the 1-indexed
k: the formula usesk - 1. - Assuming the recursion base is
k == 1: the base isn == 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.