K-th Symbol in Grammar
Medium · Backtracking · Math · Recursion · Bit Manipulation
Problem
Build a table of rows as follows. Row 1 is the single symbol 0. Each later row is made from the row above it by replacing every 0 with 01 and every 1 with 10, so row 2 is 01, row 3 is 0110 and row 4 is 01101001.
Given n and k, return the k-th symbol (1-indexed) of row n.
Examples
Input: n = 3, k = 3 Output: 1
Row 3 is 0110, and its third symbol is 1.
Input: n = 4, k = 5 Output: 1
Row 4 is 01101001, and its fifth symbol is 1.
Input: n = 1, k = 1 Output: 0
Row 1 is just 0.
Constraints
- 1 <= n <= 30
- 1 <= k <= 2^(n - 1)
Approaches
- Baseline: build row n — time O(2^n), space O(2^n)
Follow-up
The rows are prefixes of the Thue–Morse sequence: symbol k is the parity of the one-bits of k - 1. Each row is also the row above followed by its complement, which gives a second recursion. The use cases ask for the k-th letter when each copy shifts letters instead of flipping bits, and for the number of 1s in a prefix of a row.
Related problems
Start free on Cariara · Coding problems · System design studio
