628. Steady Difference Numbers
A lock designer wants every n-digit code in which any two neighbouring digits differ by exactly k. Codes may not start with the digit 0, with one exception: when n = 1 the single digit may be any of 0 to 9. A difference of 0 is allowed, in which case neighbouring digits are equal.
Return all such codes as integers, sorted from smallest to largest, with no duplicates. Build the codes digit by digit and drop a branch the moment the next digit would fall outside 0..9.
Example 1
- Input:
- n = 3, k = 7
- Output:
- [181,292,707,818,929]
- Explanation:
A difference of 7 is possible only between 0 and 7, 1 and 8, or 2 and 9, so the valid codes are
181,292,707,818and929.
Example 2
- Input:
- n = 2, k = 0
- Output:
- [11,22,33,44,55,66,77,88,99]
- Explanation:
With difference 0, a two-digit code repeats its digit:
11,22up to99.
Example 3
- Input:
- n = 1, k = 4
- Output:
- [0,1,2,3,4,5,6,7,8,9]
- Explanation:
One-digit codes have no neighbouring pair, so every digit from 0 to 9 qualifies.
Constraints
- 1 ≤
n≤ 7 - 0 ≤
k≤ 9
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(9 * 2^n)
- Space
- O(n)