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:
- Start with numbers from
1
to9
(as numbers can't begin with 0 except for the number0
itself). - Compute for next digit by adding
K
to the last digit and subtractingK
from the last digit. - 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 addK
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.
Got a question?ย Ask the Teaching 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.