Pattern visualizer
K-th Symbol in Grammar
Building row n by string replacement costs O(2^n) time and space, since each row doubles in length. But the first half of row n is always an exact copy of row n - 1, and the second half is its exact bitwise complement, because that is literally how the replacement rule expands each symbol. So instead of building anything, just ask which half index k falls into: left half, recurse into row n - 1 at the same index; right half, shift the index back by the halfway point and recurse, then flip whatever bit comes back. That is one recursive call per level, so O(n) time and O(n) stack depth. Animated on: n = 4, k = 5. Row 4 is built by replacing every 0 with 01 and every 1 with 10 in row 3, starting from row 1 = "0". Answer: 1..
Divide and conquer: which half, then flip or copy
kthSymbol(4, 5): row 4 is row 3 followed by its bitwise complement, split exactly at mid=2^(4-2)=4. k=5 decides which half we're in.
1FUNCTION kthSymbol(n, k)2 IF n = 13 RETURN 04 mid <- 2^(n - 2)5 IF k <= mid6 RETURN kthSymbol(n - 1, k)7 ELSE8 RETURN 1 - kthSymbol(n - 1, k - mid)
← / → step · space play · Home restart