← Amazon questions

K-th Symbol in Grammar

Filed under Amazon · Also reported at Editorialist YX

Free read 3 of 3

Confirm 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

  1. Confirm 1-based indexing for both row and k.

Solution

O(N) time, O(N) space for recursion stack

Python
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.