Leetcode 967. Numbers With Same Consecutive Differences

Problem Explanation:

The goal of the problem is to produce all numbers of a certain length (N) wherein the difference between each consecutive digit is a specific amount (K). The tricky part here is that these numbers can't start with a leading zero, unless the number itself is zero. The solution can be returned in any order.

Let's walk through an example:

For instance, given N = 3 and K = 7, we need to find all 3-digit numbers where the difference between each consecutive digit is 7.

We can do the following:

1. Start with numbers from 1 to 9 (as numbers can't begin with 0 except for the number 0 itself).
2. Compute for next digit by adding K to the last digit and subtracting K from the last digit.
3. If next digit is in the range from 0 to 9, Repeat the above process recursively until N becomes 0

As per our example, for N = 3 and K = 7, the output would be [181,292,707,818,929].

An important thing to note is that if K is 0 then we can form numbers like 111, 222, 333,.... till 999.

Approach of the Solution:

The solution uses a Depth First Search (DFS) algorithm.

• Starting from the numbers 1 to 9, we either subtract K or add K to each number.
• If this result falls between 0 and 9, it's added to the last digit of our current number and we call the function recursively until N becomes 0.

When N hits 0, we know that we have a number with the required number of digits and it's added to our result set.

Python Solution:

1
2python
3class Solution:
4    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
5        if N == 1: return list(range(10))
6        ans = []
7        def DFS(n, num):
8            if n == 0:
9                return ans.append(num)
10            lastdig = num%10
11            if lastdig >= K: DFS(n-1, num*10 + lastdig-K)
12            if lastdig + K < 10 and K: DFS(n-1, num*10 + lastdig+K)
13        for num in range(1, 10):
14            DFS(N-1, num)
15        return ans

Java Solution:

1
2java
3class Solution {
4    public int[] numsSameConsecDiff(int N, int K) {
5        if (N == 1) {
6            int[] output = new int[10];
7            for (int i = 0; i < 10; i++) {
8                output[i] = i;
9            }
10            return output;
11        }
12
13        List<Integer> results = new ArrayList<>();
14        for (int num = 1; num < 10; num++) {
15            this.DFS(N - 1, num, K, results);
16        }
17        return results.stream().mapToInt(i->i).toArray();
18    }
19
20    private void DFS(int N, int num, int K, List<Integer> results) {
21        if (N == 0) {
22            results.add(num);
23            return;
24        }
25
26        int tailDigit = num % 10;
27        if (tailDigit + K < 10) {
28            this.DFS(N - 1, 10 * num + tailDigit + K, K, results);
29        }
30        if (tailDigit - K >= 0) {
31            this.DFS(N - 1, 10 * num + tailDigit - K, K, results);
32        }
33    }
34}

These solutions use a recursive DFS method which checks each individual digit. By starting with a digit (1-9) and repeating until N equals 0, they add the number to the output if the current processed number has N digits. If the last digit of the current number is larger than or equal to K, it recurses with 10 times the current number plus the last digit minus K. The solution also accounts for numbers where K is 0.

Both the Java and Python solutions use similar algorithms, using recursion to systematically construct each number and then add it to a results list if it meets the required criteria.JavaScript Solution:

1
2javascript
3var numsSameConsecDiff = function(N, K) {
4    if (N === 1) return [...Array(10).keys()]; // returns [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
5    
6    let result = [];
7    const DFS = (n, num) => {
8        if(n === 0){
9            result.push(num);
10            return;
11        }
12        let lastDig = num % 10;
13
14        if(lastDig >= K) DFS(n-1, num*10 + lastDig - K);
15        if(lastDig+K < 10 && K > 0) DFS(n-1, num*10 + lastDig+K);
16    };
17    for(let num = 1; num < 10; num++){
18        DFS(N-1, num);
19    }
20    return result;
21};

The JavaScript solution is similar to those in Python and Java, making use of Depth-First Search and recursion. Starting from numbers 1 to 9, we use the DFS function to add or subtract K from the last digit of the current number. If the updated number lies between 0 and 9, we append it to the number and recursively call the DFS function again until we've constructed a number that has N digits. If N equals 0, we push the current number to the result array, this signifies that we've constructed a number with N digits that meets the required criteria. This solution is efficient and helps in understanding DFS algorithm and how to use it to solve this particular problem. If K is 0, each digit in the number will be the same, so the solution takes this into account by only adding K to the last digit if K is not equal to 0. If N is 1, the solution returns an array from 0 to 9.