#779 K-th Symbol in Grammar
frequently reported atGoogleGoldman SachsMicrosoftAmazonBloomberg
the problem
In plain words
Row 1 is "0". To build each next row, replace every 0 with "01" and every 1 with "10". Return the k-th symbol (1-indexed) of row n.
in n = 1, k = 1
out 0
in n = 2, k = 2
out 1
Row 2 is "01".
in n = 3, k = 3
out 1
Row 3 is "0110".
- 1 ≤ n ≤ 30
- 1 ≤ k ≤ 2ⁿ⁻¹
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternRecursion on a smaller inputBit tricks (shift, mask, lowest set bit)
Each symbol has a parent in the row above: position (k + 1) / 2. Odd k is a left child (copies the parent); even k is a right child (flips it). So ask the parent — one call per row.
solutions
From brute force to optimal
Literally generate rows 1..n as strings and read position k.
- Start with "0".
- Expand n − 1 times (each row doubles).
- Return row[k − 1].
Row n has 2ⁿ⁻¹ characters — over 500 million for n = 30.
The last row must be stored.
class Solution { public int kthGrammar(int n, int k) { StringBuilder row = new StringBuilder("0"); for (int i = 1; i < n; i++) { StringBuilder next = new StringBuilder(row.length() * 2); for (int j = 0; j < row.length(); j++) next.append(row.charAt(j) == '0' ? "01" : "10"); row = next; // row i+1 is twice as long: 2^(n-1) chars at the end } return row.charAt(k - 1) - '0'; }}answer(n, k) = answer(n − 1, (k + 1) / 2), flipped if k is even.
- Base case: n == 1 → 0.
- parent = kthGrammar(n − 1, (k + 1) / 2).
- Odd k → parent; even k → 1 − parent.
One call per row, O(1) work each.
n stack frames (at most 30).
class Solution { public int kthGrammar(int n, int k) { if (n == 1) return 0; // row 1 is just "0" int parent = kthGrammar(n - 1, (k + 1) / 2); // which symbol in the row above produced me? return (k % 2 == 1) ? parent : 1 - parent; // left child copies, right child flips }}Climb the tree
Walking from the root to position k, every right turn flips the symbol. The right turns are exactly the 1-bits of k − 1.
- Return Integer.bitCount(k − 1) & 1.
bitCount is a single CPU instruction on modern JVMs (and at most 32 bits anyway).
No recursion.
class Solution { public int kthGrammar(int n, int k) { return Integer.bitCount(k - 1) & 1; // one flip per right turn = per 1-bit of (k−1) }}in the room
How to say it in the interview
talk track
- Write out rows 1–4 (0, 01, 0110, 01101001) and draw them as a binary tree — the parent relationship jumps out.
- Present the recursion; mention the bit trick as a follow-up insight, not as your first answer.
traps
- Trying to build the row: n = 30 means over half a billion characters.
- Off-by-one: k is 1-indexed, so the parent is (k + 1) / 2, not k / 2.
what they ask next
Follow-ups
Why does the bit trick work?
In the tree, the path to leaf k (0-indexed: k − 1) goes right on every 1-bit. Each right turn flips; left turns copy. So the answer is the parity of the number of 1-bits.
before you submit
Edge cases to test
- n = 1, k = 1 → 0.
- k = 1 in any row is 0: the left edge only ever copies.
- n = 30: the row has 2²⁹ ≈ 5.4·10⁸ symbols — never build it.
practise next
Similar problems
- #191Number of 1 BitsEasyin Bits
- #50Pow(x, n)Mediumin Recursion