Algorithm
Problem Name: 967. 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 <= 90 <= k <= 9
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] numsSameConsecDiff(int n, int k) {
List result = new ArrayList<>();
helper(n, k, result, new StringBuilder());
return result.stream().mapToInt(Integer::intValue).toArray();
}
private void helper(int n, int k, List < Integer> result, StringBuilder sb) {
if (sb.length() == n) {
result.add(Integer.parseInt(sb.toString()));
return;
}
for (int i = 0; i < = 9; i++) {
if (sb.isEmpty() && i == 0) {
continue;
}
if (!sb.isEmpty()
&& Math.abs(Character.getNumericValue(sb.charAt(sb.length() - 1)) - i) != k) {
continue;
}
sb.append(i);
helper(n, k, result, new StringBuilder(sb));
sb.deleteCharAt(sb.length() - 1);
}
}
}
Input
n = 3, k = 7
Output
[181,292,707,818,929]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numsSameConsecDiff = function (n, k) {
const res = []
for(let i = 1; i < = 9; i++) {
dfs(n - 1, [i])
}
return res
function dfs(num, arr) {
if(num === 0) {
res.push(+arr.join(''))
return
}
for(let i = 0; i <= 9; i++) {
if(Math.abs(i - arr[arr.length - 1]) === k) {
arr.push(i)
dfs(num - 1, arr)
arr.pop(>
}
}
}
}
Input
n = 3, k = 7
Output
[181,292,707,818,929]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numsSameConsecDiff(self, N, K):
"""
:type N: int
:type K: int
:rtype: List[int]
"""
q = {i for i in range(10)}
for _ in range(N - 1):
new = set()
for num in q:
last = num % 10
if num and 0 <= last + K <= 9:
new.add(num * 10 + last + K)
if num and 0 <= last - K <= 9:
new.add(num * 10 + last - K)
q = new
return list(q)
Input
n = 2, k = 1
Output
[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0967_NumbersWithSameConsecutiveDifferences
{
public int[] NumsSameConsecDiff(int N, int K)
{
var resutls = new List < int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 2; i < = N; i++)
{
var temp = new List<int>();
foreach (var num in resutls)
{
var digit = num % 10;
if (num > 0 && K > 0 && digit - K >= 0)
temp.Add(num * 10 + digit - K);
if (num > 0 && digit + K < 10)
temp.Add(num * 10 + digit + K);
}
resutls = temp;
}
return resutls.ToArray();
}
}
}
Input
n = 2, k = 1
Output
[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]