Largest Stepping Number
MediumGreedy · Amazon
A non-negative integer is a stepping number if every pair of adjacent digits in its decimal representation (no leading zeros) differs by exactly 1. For example, 4565 and 10 are stepping numbers, while 4566 and 13 are not. Every one-digit number, including 0, is a stepping number.
Given a non-negative integer limit, return the largest stepping number that is less than or equal to limit.
Example 1
- Input:
- limit = 54320
- Output:
- 45678
- Explanation
- Keeping the prefix
5432forces the last digit to be 1 or 3, and both 54321 and 54323 exceed the limit. No shorter prefix of 54320 can be continued below the limit either, so the first digit drops to 4, after which the digits can climb freely: 45678.
Example 2
- Input:
- limit = 1000
- Output:
- 989
- Explanation
- No four-digit stepping number is at most 1000 (the smallest one is 1010), so the answer is the largest three-digit stepping number, 989.
Example 3
- Input:
- limit = 78
- Output:
- 78
- Explanation
- 7 and 8 differ by 1, so 78 is itself a stepping number.
Constraints
0 <= limit <= 10^15