Numbers With Same Consecutive Differences Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4

Input:
n = 2, k = 1
Output:
 [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Solution

Method 1 – Backtracking / BFS

Intuition

We can build all valid numbers by starting from each digit 1-9 and recursively (or iteratively) appending digits whose difference with the previous digit is k, until the number has n digits.

Approach

  1. For each starting digit 1-9, use DFS or BFS to build numbers of length n.
  2. At each step, append next digits that are within 0-9 and differ by k from the last digit.
  3. Avoid leading zeros by never starting with 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<int> numsSameConsecDiff(int n, int k) {
        vector<int> res;
        function<void(int, int)> dfs = [&](int num, int len) {
            if (len == n) { res.push_back(num); return; }
            int last = num % 10;
            if (last + k < 10) dfs(num*10 + last + k, len+1);
            if (k && last - k >= 0) dfs(num*10 + last - k, len+1);
        };
        for (int i = 1; i < 10; ++i) dfs(i, 1);
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func numsSameConsecDiff(n int, k int) []int {
    res := []int{}
    var dfs func(num, len int)
    dfs = func(num, len int) {
        if len == n { res = append(res, num); return }
        last := num % 10
        if last+k < 10 { dfs(num*10+last+k, len+1) }
        if k > 0 && last-k >= 0 { dfs(num*10+last-k, len+1) }
    }
    for i := 1; i < 10; i++ { dfs(i, 1) }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i < 10; ++i) dfs(n, k, i, 1, res);
        return res.stream().mapToInt(i->i).toArray();
    }
    private void dfs(int n, int k, int num, int len, List<Integer> res) {
        if (len == n) { res.add(num); return; }
        int last = num % 10;
        if (last + k < 10) dfs(n, k, num*10 + last + k, len+1, res);
        if (k > 0 && last - k >= 0) dfs(n, k, num*10 + last - k, len+1, res);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun numsSameConsecDiff(n: Int, k: Int): IntArray {
        val res = mutableListOf<Int>()
        fun dfs(num: Int, len: Int) {
            if (len == n) { res.add(num); return }
            val last = num % 10
            if (last + k < 10) dfs(num*10 + last + k, len+1)
            if (k > 0 && last - k >= 0) dfs(num*10 + last - k, len+1)
        }
        for (i in 1..9) dfs(i, 1)
        return res.toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> list[int]:
        res = []
        def dfs(num, length):
            if length == n:
                res.append(num)
                return
            last = num % 10
            if last + k < 10:
                dfs(num*10 + last + k, length+1)
            if k > 0 and last - k >= 0:
                dfs(num*10 + last - k, length+1)
        for i in range(1, 10):
            dfs(i, 1)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn nums_same_consec_diff(n: i32, k: i32) -> Vec<i32> {
        let mut res = vec![];
        fn dfs(n: i32, k: i32, num: i32, len: i32, res: &mut Vec<i32>) {
            if len == n { res.push(num); return; }
            let last = num % 10;
            if last + k < 10 { dfs(n, k, num*10 + last + k, len+1, res); }
            if k > 0 && last - k >= 0 { dfs(n, k, num*10 + last - k, len+1, res); }
        }
        for i in 1..10 { dfs(n, k, i, 1, &mut res); }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    numsSameConsecDiff(n: number, k: number): number[] {
        const res: number[] = [];
        function dfs(num: number, len: number) {
            if (len === n) { res.push(num); return; }
            const last = num % 10;
            if (last + k < 10) dfs(num*10 + last + k, len+1);
            if (k > 0 && last - k >= 0) dfs(num*10 + last - k, len+1);
        }
        for (let i = 1; i < 10; i++) dfs(i, 1);
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(2^n) in the worst case (k ≠ 0), otherwise O(9*n).
  • 🧺 Space complexity: O(2^n) for the recursion stack and result.