Strobogrammatic Number III
Hard · Backtracking · Array · String · Recursion · Math
Problem
A strobogrammatic number reads the same after a 180-degree rotation. Only the digits 0, 1, 6, 8 and 9 survive the rotation: 0, 1 and 8 stay themselves, while 6 and 9 turn into each other. For example, 69, 88 and 818 are strobogrammatic.
You are given two strings low and high that represent integers with low <= high. Return how many strobogrammatic numbers x satisfy low <= x <= high. Numbers are written without leading zeros, except for 0 itself.
Examples
Input: low = "0", high = "20" Output: 4
The strobogrammatic numbers in range are 0, 1, 8 and 11.
Input: low = "1000", high = "2000" Output: 5
They are 1001, 1111, 1691, 1881 and 1961.
Input: low = "50", high = "100" Output: 3
They are 69, 88 and 96; 101 is just past the end.
Constraints
- 1 <= len(low), len(high) <= 15
- low and high consist of digits only
- low <= high
- Neither has leading zeros, except for the number 0 itself
Approaches
- Generate every candidate of each length — time O(5^(L/2)), space O(5^(L/2))
Follow-up
The "count up to x" function turns any range question into two prefix questions: count(high) - count(low) + [low qualifies]. The same digit-by-digit counting works for other numbers fixed by a prefix, such as palindromes in a range.
Related problems
Start free on Cariara · Coding problems · System design studio
