Upside-Down Numbers of a Given Length
Problem
A clock maker wants every number that still reads correctly when the display is turned upside down. Rotated by 180 degrees, 0, 1 and 8 stay the same, 6 becomes 9 and 9 becomes 6, and every other digit becomes unreadable. Given n between 1 and 14, return all n-digit numbers that look the same after the rotation, as strings in ascending order. A number longer than one digit may not start with 0.
Examples
Input: n = 2
Output: ["11", "69", "88", "96"]
Why: "00" is excluded because of the leading zeroInput: n = 1
Output: ["0", "1", "8"]
Why: edge case, a lone middle digit must map to itself, so 6 and 9 cannot be usedInput: n = 3
Output: ["101", "111", "181", "609", "619", "689", "808", "818", "888", "906", "916", "986"]Hints
0 / 3
Turning the number upside down swaps its first and last digits and rotates each of them, so the outermost pair must be one of (0, 0), (1, 1), (6, 9), (8, 8) or (9, 6).
Remove that outer pair and what is left is a shorter number with the same property. So the answers of length n are built by wrapping answers of length n - 2.
Recurse on the length with base cases 0 (just the empty string) and 1 (0, 1 and 8). Wrap each inner answer in every pair, but skip the (0, 0) pair at the outermost level only.
Solution
After a 180-degree turn the first digit ends up last and rotated, so a valid number is a valid rotating pair wrapped around a shorter valid number, and the inner part has the same property at length n - 2. That makes the recursion return its answers up the call chain: build(k) asks for build(k - 2) and wraps every inner string in each of the five pairs. The base cases are length 0, which contributes the empty string, and length 1, which allows only the self-rotating digits. Inner layers may use the (0, 0) pair freely, since a zero in the middle is fine; only the outermost layer, where k equals n, skips it to avoid a leading zero. The output has about 4 × 5^(n/2 - 1) strings of length n, so time and space are O(n × 5^(n/2)).
PAIRS = [("0", "0"), ("1", "1"), ("6", "9"), ("8", "8"), ("9", "6")]
def upside_down(n):
def build(k):
if k == 0:
return [""]
if k == 1:
return ["0", "1", "8"]
return [a + mid + b
for mid in build(k - 2)
for a, b in PAIRS
if not (k == n and a == "0")] # no leading zero at the outer layer
return sorted(build(n))
print(upside_down(2)) # -> ['11', '69', '88', '96']
print(upside_down(1)) # -> ['0', '1', '8']
print(len(upside_down(3))) # -> 12
print(len(upside_down(4))) # -> 20Stuck on the idea rather than the code? Return Up or Pass Down covers it.