Hard · Recursive Symmetry
Understand → Visualise → Practice.
Rows begin with 0; each 0 expands to 01 and each 1 to 10. Return the one-indexed kth symbol in the requested row.
Row n is row n − 1 followed by its complement. So the kth symbol lies in the first half (same as row n − 1) or the second half (the flipped symbol at k − half).
Row 1 is just 0.
half = 2ⁿ⁻²: the length of row n − 1.
If k ≤ half, return the same position in row n − 1; otherwise return 1 minus the symbol at k − half.
O(n) time and O(n) recursion depth.
Building the whole row needs 2ⁿ⁻¹ symbols, which is impossible for large rows.
Read the full guide first: Recursion and Backtracking.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.