K-th Symbol in Grammar
Filed under Amazon · Also reported at Editorialist YX
Free read 3 of 3Confirm 1-based indexing for both row and k.
The question
On the 1-indexed grammar sequence where the first row is '0', every subsequent row is generated by replacing 0 with 01 and 1 with 10. Find the k-th symbol in the n-th row.
Constraints
- 1 <= n <= 30
- 1 <= k <= 2^(n-1)
Examples
- Input
- n = 2, k = 2
- Output
- 1
- Why
- Row 1: 0. Row 2: 01. The 2nd symbol is 1.
Approach
Confirm 1-based indexing for both row and k.
Generate strings row by row up to n, taking exponential time and space.
Use recursion based on the parent-child relationship. The length of row n is 2^(n-1). If k is in the first half (k <= mid), the symbol is the same as the parent in row n-1 at index k. If k is in the second half (k > mid), the symbol is the inverse of the parent at index k - mid.
n=1, k=1.
Solution
O(N) time, O(N) space for recursion stack
def kthGrammar(n: int, k: int) -> int:
if n == 1:
return 0
mid = 2 ** (n - 2)
if k <= mid:
return kthGrammar(n - 1, k)
else:
return 1 - kthGrammar(n - 1, k - mid)
Tips
- What they are testing: Test base cases like n=1, k=1, and boundary values of k for higher n.
- Common mistake: Attempting to generate the entire string, which causes memory and time limit exceedance for large n.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.