medium +25 pts

Strobogrammatic number II

Generate all numbers of length n that read the same when rotated 180 degrees.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (viewed upside down). The valid digits and their rotations are: 0 -> 0 1 -> 1 6 -> 9 8 -> 8 9 -> 6 Write a function `find_strobogrammatic(n)` that takes a positive integer `n` and returns a list of strobogrammatic numbers of exactly length `n`, sorted in ascending order. For `n = 0`, the function should return `['']` (the empty string is considered a strobogrammatic number of length 0). For `n >= 1`, numbers must not have leading zeros (e.g., for n=2, '00' is not allowed). The returned numbers should be represented as strings, not integers. Examples: - `find_strobogrammatic(1)` returns `['0', '1', '8']` - `find_strobogrammatic(2)` returns `['11', '69', '88', '96']` - `find_strobogrammatic(3)` returns `['101', '111', '181', '609', '619', '689', '808', '818', '888', '906', '916', '986']`

Constraints

1 <= n <= 14 (the number of strobogrammatic numbers is manageable, but do not generate all numbers and filter; construct them directly). Output list must be sorted in ascending numeric order (as strings). Complexity should be about O(5^(n/2)) time and space.

Example

>>> find_strobogrammatic(1)
['0', '1', '8']
>>> find_strobogrammatic(2)
['11', '69', '88', '96']
>>> find_strobogrammatic(3)
['101', '111', '181', '609', '619', '689', '808', '818', '888', '906', '916', '986']
25 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think recursively: build the number from the outside inward, pairing digits that rotate into each other.
For even length n, consider pairs of digits (0,0), (1,1), (6,9), (8,8), (9,6). For odd length, the middle digit must be one of 0, 1, 8.
Handle the leading-zero restriction by not allowing 0 as the first digit when building the outer level.
The base case for recursion: length 0 returns [''] and length 1 returns ['0','1','8'].
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.