Grow the row
Find one symbol of a row that doubles in size each time, by tracing it back to the row before. About 16 minutes.
Rows built from the row above
Row 1 is the single symbol 0. To make the next row, replace every 0 by 01 and every 1 by 10. So row 2 is 01, row 3 is 0110, row 4 is 01101001, and each row has twice as many symbols as the one before.
Row 30 has over 500 million symbols, so don't build it. Ask instead: where did the k-th symbol come from? Each symbol in a row is one of the two children of a symbol in the row above.
k = 5 parent = (k + 1) // 2 # 3 odd = k % 2 == 1 # True
Row 4, position 6. It is even, so it flips its parent, which is position (6 + 1) ÷ 2 = 3 in row 3.
Which parent, and what is the child
Positions 1 and 2 in a row come from position 1 in the row above, positions 3 and 4 from position 2, and in general position k comes from position (k + 1) divided by 2, rounded down.
The first child of a 0 is 0 (since 0 becomes 01) and of a 1 is 1 (since 1 becomes 10). The second child is the opposite. So an odd position copies its parent and an even position flips it. Only n calls are needed, however large the row is.
Which position in the row above produces position 7 in the current row?
- APosition 4, since (7 + 1) ÷ 2 = 4
- BPosition 3
- CPosition 7
Show the answer
Position 4, since (7 + 1) ÷ 2 = 4. Positions 7 and 8 are the two children of position 4.
Grow the row
Row 1 is the single symbol 0. Each following row is made from the row before by replacing every 0 with 01 and every 1 with 10. For example row 2 is 01, row 3 is 0110 and row 4 is 01101001. Return the k-th symbol (counting from 1) of row n, as the number 0 or 1.
n = 4, k = 6 → 0
1 ≤ n ≤ 30 · 1 ≤ k ≤ 2^(n − 1)