K-th Symbol in Grammar

Problem

A fractal signal generator starts with the symbol 0 and applies one rule forever: each 0 becomes 01, each 1 becomes 10. Row 1 is 0, row 2 is 01, row 3 is 0110, and so on - each row doubles the last. Given a row number n and a position k (1-indexed), return the symbol at that position without materializing the row.

Example 1:

Input: n = 4, k = 5
Output: 1
Explanation: row 4 is 01101001; the 5th symbol is 1.

Example 2:

Input: n = 3, k = 4
Output: 0
Explanation: row 3 is 0110; the last symbol is 0 - two flips away from the root cancel out.

Example 3:

Input: n = 5, k = 12
Output: 1
Explanation: walking parents: 12 -> 6 -> 3 -> 2 -> 1 flips three times (12, 6, and 2 are even positions) and copies once (3 is odd), landing on 1.

Constraints:

• 1 <= n <= 30
• 1 <= k <= 2^(n-1)

Rows:
1: 0
2: 0 1
3: 0 1 1 0
4: 0 1 1 0 1 0 0 1
   positions 1..8; each position's parent in the row above is (k+1)//2.

Solution Breakdown

Approach - walk the parent chain instead of generating the grammar.

Row n holds 2^(n-1) symbols - materializing it is exponential and dead on arrival for n near 30. But the grammar is a rewrite system where every symbol has exactly one parent: children 2j-1 and 2j of row n both descend from position j of row n-1, so the parent of (n, k) is (n-1, (k+1)//2). And both rewrite rules share a uniform shape: 0 -> 01 and 1 -> 10 each put the original symbol first and its complement second. That makes the child rule trivial: an odd position copies the parent, an even position flips it. The recursion is therefore three lines - get the parent's value, copy it if k is odd, complement it if k is even - with the base case (1, 1) = 0, the grammar's seed. Each step halves k and decrements n, so the chain always terminates at row 1 after n - 1 calls and touches no row data at all.

Trace (5, 12): 12 is even - flip parent (4, 6); 6 is even - flip parent (3, 3); 3 is odd - copy parent (2, 2); 2 is even - flip parent (1, 1) = 0, giving (2, 2) = 1; copying forward leaves (3, 3) = 1; the two flips cancel, (4, 6) = 0; the final flip yields 1. The double-cancellation is structural: flips are complements mod 2, so the answer is really the parity of even-steps along the chain - equivalently the popcount of k - 1 in binary, since each set bit of k - 1 marks one "take the second child" decision.

Edge cases - k = 1 in any row never leaves the odd-copy chain, so the leading symbol is always 0 (consistent with 0 always rewriting to 01); the constraints guarantee k never exceeds the row's length.

Complexity - O(n) time, one constant-work call per level; O(n) stack space for the recursion, O(1) for the iterative parent-walk that tracks flip parity in a loop. Either way the exponential row is never touched - that is the entire point of the problem.