K-th Symbol in Grammar
A medium Recursion interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Recursion
- Sheets
- 1
- Core for
- 11 roles
The problem
The k-th symbol in the grammar is defined by a table where row 1 is 0, and each subsequent row is derived from the previous row by replacing each 0 with 01 and each 1 with 10. Find the k-th symbol in row n.
Example 1
- Input
- n = 1, k = 1
- Output
- 0
Example 2
- Input
- n = 2, k = 1
- Output
- 0
- Why
- Row 2 is 01, so the first symbol is 0.
Example 3
- Input
- n = 2, k = 2
- Output
- 1
- Why
- Row 2 is 01, so the second symbol is 1.
Constraints
- 1 <= n <= 30
- 1 <= k <= 2^(n-1)
How to think about it
Updated 2026-09-29The first half of row n is identical to the whole of row n - 1, while the second half is its exact bitwise complement. You never need to build any row: check whether k falls in the left or right half, flip the bit if right, and trace back to the parent index.
Approaches, worst first
Brute force row generation
time O(2^n) · space O(2^n)
Generate strings row by row using character replacement. Explodes memory and runtime exponentially, as row 30 contains 2^29 characters (over 500 million bytes).
Divide and conquer parent lookup
time O(n) · space O(n)
Compare k to the midpoint 2^(n-2). If k <= midpoint, query row n - 1 at k directly; otherwise query row n - 1 at k - midpoint and invert the resulting bit.
Bitwise parity countWrite this one
time O(1) · space O(1)
The value of symbol k (0-indexed as k - 1) equals the parity of the number of set bits in k - 1 (the Thue-Morse sequence). Can be evaluated with a single popcount call.
Where people lose marks · 3
- Integer overflow when calculating row midpoint using 1 << (n - 1) if using 32-bit signed shift at n = 32.
- Forgetting that converting k from 1-based to 0-based is required before bit manipulation.
- Flipping bit logic: 0 becomes 1 and 1 becomes 0, not arithmetic negation.
The theory behind it
Recursion — the ground this problem stands on. All Recursion problems
What Recursion is
Recursion is a nesting doll that opens to reveal an identical smaller doll inside. In programming, a function solves a substantial problem by delegating smaller versions of the exact same question to fresh invocations of itself. Each invocation operates on shrunken input until hitting an irreducible foundation called a base case, which returns an immediate answer and permits the waiting cascade to resolve backwards.
When to reach for it
Reach for recursion when a problem possesses self-similar subproblems, such as traversing branched tree structures, exploring graph pathways, or generating combinations. Phrases asking for all permutations, subset generation, exhaustive maze navigation, or hierarchical file system traversals signal recursive decomposition. It is natural whenever the answer to a large instance depends on assembling identical solutions for smaller subsets.
How the pattern works
Structure every recursive method around two mandatory stages: the termination stop and the shrinking recurrence. Write the base condition first so the function exits before attempting further execution. Next, trust the recursive call to return valid answers for smaller inputs without mentally unwinding every level at once. Pass accumulation state forward through parameters, or combine child return values on the ascent phase once deeper calls return.
More Recursion problems
Target Roles
Core requirement for 11 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .