Symbol In A Doubling Row
Problem
Row 1 is the single symbol 0. Each later row is made from the one above by replacing every 0 with 01 and every 1 with 10, so row n has 2 to the n minus 1 symbols. Given a row number n and a position k counted from 1, return the symbol at that position. Row 30 has over half a billion symbols, so building rows is not an option.
Examples
Input: n = 4, k = 5
Output: 1
Why: the rows are 0, 01, 0110, 01101001Input: n = 2, k = 2
Output: 1Input: n = 1, k = 1
Output: 0
Why: edge case, the seed row itselfHints
0 / 3
Every symbol in a row was produced by exactly one symbol in the row above. Work out which one.
Positions 2i minus 1 and 2i both come from position i of the previous row. The first of the two copies its parent and the second is the opposite of its parent.
Recurse on the row above with position (k + 1) // 2 to get the parent symbol. Return it unchanged when k is odd and flipped when k is even. Row 1 is the base case and returns 0.
Solution
Each symbol in row n is one of the two children of a symbol in row n minus 1: position k comes from position (k + 1) // 2, and an odd k is the left child, which copies its parent, while an even k is the right child, which flips it. So the question for row n reduces to the same question one row up with the position halved, until row 1 answers 0. Only one call is made per row, so time and stack depth are both O(n), and nothing close to the full row is ever built.
def symbol(n, k):
if n == 1:
return 0 # the seed row is a single 0
parent = symbol(n - 1, (k + 1) // 2) # the symbol that produced position k
return parent if k % 2 == 1 else 1 - parent # left child copies, right flips
print(symbol(4, 5)) # -> 1
print(symbol(2, 2)) # -> 1
print(symbol(1, 1)) # -> 0
print(symbol(30, 2 ** 29)) # -> 1Stuck on the idea rather than the code? Recursion Basics covers it.