LeetCode Numbers With Same Consecutive Differences Solution

Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order.

Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

Example 1:

Input: n = 3, k = 7

Output: [181,292,707,818,929]

Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: n = 2, k = 1

Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Constraints:

• 2 <= n <= 9
• 0 <= k <= 9

We want to build up the numbers from the leftmost digit to the rightmost. Since n is >= 2 and there should not be leading zeros, we will start from one digit (1-9) and call our backtracking helper to construct the next digits. Here, our path (num in the implementation) will store an integer instead of a list to save space and time.

We want to apply backtracking1 template. We fill in the logic:

• is_leaf: start_index == n, when the constucted number contains n digits.
• get_edges: the next digit can be cur_digit +- k
• is_valid: cur_digit + k <= 9 and cur_digit - k >= 0 to avoid the next digit being out of bound. Note that in the implementation, if k=0 then cur_digit+k == cur_digit - k, we must avoid the duplicate by checking whether k=0.

Implementation

1def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
2    def dfs(start_index, num):
3        if start_index == n:  # num is n digits, add to ans
4            ans.append(num)
5            return
6        cur_digit = num % 10        # current digit
7        if (cur_digit - k >= 0):
8            dfs(start_index + 1, num * 10 + (cur_digit - k))
9        if (cur_digit + k <= 9 and k != 0): # avoid duplicate when k = 0
10            dfs(start_index + 1, num * 10 + (cur_digit + k))
11    ans = []
12    for i in range(1, 10):  # first digit can be 1-9
13        dfs(1, i)
14    return ans