Numbers With Same Consecutive Differences — Solution
Numbers With Same Consecutive Differences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Numbers With Same Consecutive Differences is a medium coding problem on breadth-first search and backtracking, asked in Amazon and Flipkart interviews.
- Difficulty: Medium
- Topics: Breadth-First Search, Backtracking
- Asked at: Amazon, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return every n-digit positive integer in which any two neighbouring digits differ by exactly k (in absolute value). Numbers may not have leading zeros, so the first digit is between 1 and 9 — but later digits may be 0.
Return the numbers in ascending order.
Example 1
Input: n = 3, k = 7
Output: [181,292,707,818,929]
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]
Example 3
Input: n = 2, k = 0
Output: [11,22,33,44,55,66,77,88,99]
Explanation: With k = 0 every digit repeats the first; each number appears once.
Constraints
2 <= n <= 90 <= k <= 9
Hints for Numbers With Same Consecutive Differences
Hint 1
Build the numbers digit by digit: after a digit
d, the next digit can only bed - kord + k, if it stays between 0 and 9.Hint 2
Start from each first digit 1..9 and extend depth-first (or level by level) until the number has
ndigits.Hint 3
When
k = 0,d - kandd + kare the same digit — take it once, or you will list numbers twice.
How to solve Numbers With Same Consecutive Differences
Every valid number is a walk of length n on the digits where each step moves by ±k. Enumerate the walks from each non-zero first digit.
Approach
- For each first digit
ffrom 1 to 9, rundfs(f, 1). dfs(num, len): iflen == n, recordnum. Otherwise letd = num % 10and recurse onnum * 10 + (d - k)whend - k >= 0, then onnum * 10 + (d + k)whenk > 0andd + k <= 9.- Because every number has the same length, trying smaller digits first at every position produces them in ascending order.
Why it works
Each number is determined by its digits, and each digit after the first is forced to be one of at most two values, so the search lists every valid number exactly once (the k > 0 test stops the duplicate branch when the two candidates coincide).
Complexity
- Time —
O(9 · 2^(n-1)) numbers at most - Space —
O(n) recursion depth besides the output
Pitfalls
- The first digit cannot be 0, but later digits can.
- k = 0 makes both candidates equal; branching twice duplicates every number.
- The largest value, 989898989, still fits in a 32-bit int.
Reference solution
Python
from typing import List
def numsSameConsecDiff(n: int, k: int) -> List[int]:
out = []
def dfs(num, length):
if length == n:
out.append(num)
return
d = num % 10
if d - k >= 0:
dfs(num * 10 + d - k, length + 1)
if k > 0 and d + k <= 9:
dfs(num * 10 + d + k, length + 1)
for f in range(1, 10):
dfs(f, 1)
return outJava
public static int[] numsSameConsecDiff(int n, int k) {
List<Integer> out = new ArrayList<>();
for (int f = 1; f <= 9; f++) consecDfs(f, 1, n, k, out);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}
static void consecDfs(int num, int len, int n, int k, List<Integer> out) {
if (len == n) {
out.add(num);
return;
}
int d = num % 10;
if (d - k >= 0) consecDfs(num * 10 + d - k, len + 1, n, k, out);
if (k > 0 && d + k <= 9) consecDfs(num * 10 + d + k, len + 1, n, k, out);
}C++
void consecDfs(int num, int len, int n, int k, vector<int>& out) {
if (len == n) {
out.push_back(num);
return;
}
int d = num % 10;
if (d - k >= 0) consecDfs(num * 10 + d - k, len + 1, n, k, out);
if (k > 0 && d + k <= 9) consecDfs(num * 10 + d + k, len + 1, n, k, out);
}
vector<int> numsSameConsecDiff(int n, int k) {
vector<int> out;
for (int f = 1; f <= 9; f++) consecDfs(f, 1, n, k, out);
return out;
}JavaScript
var numsSameConsecDiff = function(n, k) {
var out = [];
var dfs = function(num, len) {
if (len === n) {
out.push(num);
return;
}
var d = num % 10;
if (d - k >= 0) dfs(num * 10 + d - k, len + 1);
if (k > 0 && d + k <= 9) dfs(num * 10 + d + k, len + 1);
};
for (var f = 1; f <= 9; f++) dfs(f, 1);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Backtracking