MediumMathBit ManipulationRecursionUpdated Sep 2026

779. K-th Symbol in Grammar

Asked at DE Shaw

Difficulty

Medium

Time

O(log k)

Space

O(1)

Pattern

Math

Companies

1

Problem

We build rows of 0s and 1s. Row 1 is just 0. To get the next row, we read the current row left to right and replace each symbol: every 0 becomes 01, and every 1 becomes 10. So each row is exactly twice as long as the one before it.

Given two integers n and k, return the k-th symbol (counting from 1) in row n.

You do not need to build the rows. Row n has 2^(n-1) symbols, which is far too many to write out when n is up to 30. Instead, notice that a symbol's value depends only on the path of choices that led to it from the top.

Rows double in length

row 100Row 1 starts as a single 0.row 20101The 0 becomes 01, so the 2nd symbol of row 2 is 1.row 301100123Row 3 expands each symbol again: 0→01 and 1→10.
Each row is built by expanding every symbol of the row above into a pair.

Constraints

  • ●1 <= n <= 30
  • ●1 <= k <= 2^n - 1

Examples

Example 1
Inputn = 1, k = 1
Output0
WhyRow 1 is just the single symbol 0, so the 1st symbol is 0.
Example 2
Inputn = 2, k = 1
Output0
WhyRow 2 is 01. The 1st symbol is the first half of the pair 01, which is 0.
Example 3
Inputn = 2, k = 2
Output1
WhyRow 2 is 01. The 2nd symbol is the second half of the pair 01, which is 1.

Asked At

1 companies
CompanyDifficulty
DE ShawMediumView all DE Shaw questions →

How to Think About It

1

Row n has 2^(n-1) symbols; generating it is exponential.

2

Key insight: symbol k in row n comes from symbol ceil(k / 2) in row n - 1. If k is odd, it is the first child and equals its parent; if k is even, it is the second child and is the flip of its parent.

3

That gives a recursion of depth n: kth(n, k) = kth(n-1, (k+1)/2) if k is odd, else 1 - kth(n-1, k/2).

4

Bit trick: going from row 1 down, the symbol flips once for every step that takes the second child. Those steps correspond exactly to the 1 bits of k - 1. So the answer is popcount(k - 1) % 2.

5

Walkthrough: n = 2, k = 2: k - 1 = 1 has one set bit -> answer 1 (row 2 is 01).

Optimal Approach

Step 1: Observe that each position's binary path from the root is given by the bits of k - 1.
Step 2: Every 1 bit means "take the second child", which flips the symbol.
Step 3: Return popcount(k - 1) % 2.

n does not even affect the answer, as long as k is within row n.

Time: O(log k). Space: O(1).

Trace k back to its parent

k = 2, even → flip, k = 1k = 1, odd → keep, k = 0k = 0 → stop, base is 0flips = 1 → answer 1Walking k = 2 back up to row 1.k odd → same as parentk even → flip of parentanswer = popcount(k - 1) % 2
Each step halves k. An even k means we took the second child, which flips the symbol.
ComplexityTime O(log k)Space O(1)We only count the set bits of k - 1; n never enters the computation.

What Trips People Up in Real Interviews

1

Building the rows as strings. Row 30 has over 500 million symbols.

2

Mixing up which child keeps the parent's value. With 1-indexed k, odd positions keep it and even positions flip it.

3

Presenting the bit trick without justification. Show the recursive parent relation first, then explain why it reduces to counting 1 bits.

4

Off-by-one using k instead of k - 1.

Solution Code

O(log k) time
def kthGrammar(n, k):
    return bin(k - 1).count('1') % 2

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the K-th Symbol in Grammar problem?

K-th Symbol in Grammar builds rows of 0s and 1s: row 1 is `0`, and each next row replaces every `0` with `01` and every `1` with `10`. It asks for the `k`-th symbol of row `n`. Rows double in length, so generating them is hopeless for `n = 30` — you need to trace the symbol back to its ancestors.

How do you solve K-th Symbol in Grammar?

The optimal approach runs in O(log k) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask K-th Symbol in Grammar?

K-th Symbol in Grammar is asked at DE Shaw. It is a medium difficulty problem.

What are common mistakes on K-th Symbol in Grammar?
  • Building the rows as strings. Row 30 has over 500 million symbols.
  • Mixing up which child keeps the parent's value. With 1-indexed `k`, odd positions keep it and even positions flip it.
  • Presenting the bit trick without justification. Show the recursive parent relation first, then explain why it reduces to counting 1 bits.
  • Off-by-one using `k` instead of `k - 1`.