Numbers With Same Consecutive Differences

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

Solution

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Implementation


Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄