1773. Rising Digit Numbers
A locker company only issues access codes whose decimal digits strictly increase from left to right, for example 358 or 1289, so that codes are easy to remember. A single digit also counts as a valid code, but 11, 20 and 4321 do not. Given the integers low and high, return every such code that lies in the inclusive range [low, high].
The result must be sorted in ascending order; if no code is in range, return an empty list. Do not scan the whole range, which can contain a billion numbers. Instead use backtracking over the digit choices: extend a prefix with a larger digit than its last one and stop extending as soon as the value exceeds high. Only 511 candidates exist in total, so the time is O(511 log 511) including the final sort, and the space is O(1) besides the answer.
Example 1
- Input:
- low = 1, high = 20
- Output:
- [1,2,3,4,5,6,7,8,9,12,13,14,15,16,17,18,19]
- Explanation:
1 to 9 qualify, and among 10 to 20 only 12 to 19 do.
Example 2
- Input:
- low = 100, high = 150
- Output:
- [123,124,125,126,127,128,129,134,135,136,137,138,139,145,146,147,148,149]
- Explanation:
Starting with 1 and growing, the numbers 123 to 129, 134 to 139 and 145 to 149 qualify.
Constraints
1 ≤ low ≤ high ≤ 109 (at most 511 results)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(2^9 log 2^9)
- Space
- O(1)