Numbers With Same Consecutive Differences
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating all possible integers of length n and then checking each one to see if it meets the specified condition. The integers of length n range from 10^(n-1) to 10^n - 1.
Algorithm
- Initialize an empty list
result. - Calculate the range of n-digit numbers:
start = 10^(n-1)andend = 10^n - 1. - Iterate through each number
numfromstarttoend. - For each
num, create a helper functionisValid(num, k)to check if it satisfies the condition. - Inside
isValid, repeatedly extract the last two digits of the number and check if their absolute difference isk. - If any pair of consecutive digits does not satisfy the condition, the number is invalid.
- If all pairs are valid, add the number to the
resultlist. - Finally, convert the list to an array and return it.
Walkthrough
The algorithm iterates through every number in the valid range for an n-digit number. For each number, it converts it into a sequence of digits. Then, it checks if the absolute difference between every pair of consecutive digits is equal to k. If the condition holds for all pairs of digits, the number is added to the result list. This method is simple to conceptualize but highly inefficient due to the vast number of candidates it needs to check.
import java.util.ArrayList;import java.util.List; class Solution { public int[] numsSameConsecDiff(int n, int k) { List<Integer> result = new ArrayList<>(); long start = (long) Math.pow(10, n - 1); long end = (long) Math.pow(10, n) - 1; for (long i = start; i <= end; i++) { if (isValid(i, k)) { result.add((int) i); } } return result.stream().mapToInt(i -> i).toArray(); } private boolean isValid(long num, int k) { long currentNum = num; while (currentNum >= 10) { long lastDigit = currentNum % 10; currentNum /= 10; long secondLastDigit = currentNum % 10; if (Math.abs(lastDigit - secondLastDigit) != k) { return false; } } return true; }}Complexity
Time
O(n * 10^n). The loop runs `9 * 10^(n-1)` times. Inside the loop, the `isValid` function takes O(n) time to check all `n-1` pairs of digits. For `n=9`, this is prohibitively slow.
Space
O(N), where N is the number of valid integers found. This space is used to store the result. The auxiliary space required for checking each number is O(1).
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient and will time out for larger values of
n(e.g.,n > 4).It explores a massive search space (
9 * 10^(n-1)numbers), most of which is irrelevant to the solution.
This approach builds the numbers digit by digit, level by level. It starts with single-digit numbers and iteratively adds new digits that satisfy the condition, effectively performing a Breadth-First Search (BFS) on the solution space.
Algorithm
- Initialize a list or queue,
currentLevel, with single-digit numbers from 1 to 9. - Loop
n-1times, as we already have numbers of length 1. - In each iteration, create a new empty list
nextLevel. - For each number
numincurrentLevel:- Get the last digit:
lastDigit = num % 10. - Calculate the two possible next digits:
lastDigit + kandlastDigit - k. - If a
nextDigitis valid (between 0 and 9), form a new numbernum * 10 + nextDigitand add it tonextLevel. - If
kis 0, the two options are the same, so only add the new number once.
- Get the last digit:
- After iterating through all numbers in
currentLevel, replacecurrentLevelwithnextLevel. - After the loops complete,
currentLevelwill contain all valid n-digit numbers.
Walkthrough
We can think of this problem as traversing a tree where each node is a number, and its children are numbers formed by appending a valid next digit. BFS explores this tree level by level. We start with a list containing all single-digit numbers from 1 to 9. Then, we iterate n-1 times. In each iteration, we generate numbers of the next length by taking each number from the current list, finding its last digit, and appending a new valid digit. This process continues until we have generated all numbers of length n.
import java.util.ArrayList;import java.util.List; class Solution { public int[] numsSameConsecDiff(int n, int k) { List<Integer> currentLevel = new ArrayList<>(); for (int i = 1; i <= 9; i++) { currentLevel.add(i); } // We already have numbers of length 1, so we iterate n-1 times for (int i = 2; i <= n; i++) { List<Integer> nextLevel = new ArrayList<>(); for (int num : currentLevel) { int lastDigit = num % 10; // Option 1: Add k int nextDigit = lastDigit + k; if (nextDigit <= 9) { nextLevel.add(num * 10 + nextDigit); } // Option 2: Subtract k (if k is not 0 to avoid duplicates) if (k != 0) { nextDigit = lastDigit - k; if (nextDigit >= 0) { nextLevel.add(num * 10 + nextDigit); } } } currentLevel = nextLevel; } return currentLevel.stream().mapToInt(i -> i).toArray(); }}Complexity
Time
O(2^n). The number of valid numbers can grow by a factor of at most 2 at each step. The process has `n-1` steps. The total number of nodes generated is proportional to `9 * 2^(n-1)`.
Space
O(2^n). The space is dominated by the list used to store the numbers at each level. The size of this list can be up to `9 * 2^(n-1)`.
Trade-offs
Pros
Much more efficient than brute force.
Avoids recursion, which can prevent stack overflow for very large
n(though not an issue with the given constraints).Conceptually clear, building numbers level by level.
Cons
Uses more auxiliary space than the recursive DFS approach because it needs to store all numbers of a given length at once.
This is a classic backtracking approach that builds the numbers digit by digit using recursion. It explores one full path to construct a number of length n before backtracking to explore other possibilities. This is equivalent to a Depth-First Search (DFS) on the implicit tree of numbers.
Algorithm
- Initialize an empty list
results. - Create a recursive helper function, e.g.,
dfs(length, currentNum). - The main function will loop through the first digits from 1 to 9 and call
dfs(1, i)for each. - Inside
dfs(length, currentNum):- Base Case: If
length == n, addcurrentNumtoresultsand return. - Recursive Step:
- Get the last digit:
lastDigit = currentNum % 10. - Calculate
nextDigit1 = lastDigit + k. If it's a valid digit (0-9), make a recursive call:dfs(length + 1, currentNum * 10 + nextDigit1). - If
k != 0, calculatenextDigit2 = lastDigit - k. If it's a valid digit, make another recursive call:dfs(length + 1, currentNum * 10 + nextDigit2).
- Get the last digit:
- Base Case: If
- After the initial calls complete, convert the
resultslist to an array.
Walkthrough
We define a recursive helper function that builds a number digit by digit. The function takes the current number and its length as parameters. The base case for the recursion is when the number reaches the desired length n, at which point it's added to a list of results. In the recursive step, we find the last digit of the current number and explore two possible branches by appending lastDigit + k and lastDigit - k, provided they are valid digits (0-9). The process starts by calling this recursive function for each possible starting digit (1-9).
import java.util.ArrayList;import java.util.List; class Solution { private List<Integer> results; private int N; private int K; public int[] numsSameConsecDiff(int n, int k) { this.results = new ArrayList<>(); this.N = n; this.K = k; for (int i = 1; i <= 9; i++) { dfs(1, i); } return results.stream().mapToInt(i -> i).toArray(); } private void dfs(int length, int currentNum) { // Base case: if we have a number of length N if (length == N) { results.add(currentNum); return; } int lastDigit = currentNum % 10; // Option 1: Add K int nextDigit = lastDigit + K; if (nextDigit <= 9) { dfs(length + 1, currentNum * 10 + nextDigit); } // Option 2: Subtract K (avoid duplicates if K is 0) if (K != 0) { nextDigit = lastDigit - K; if (nextDigit >= 0) { dfs(length + 1, currentNum * 10 + nextDigit); } } }}Complexity
Time
O(2^n). The recursion tree has a branching factor of at most 2 and a depth of `n`. The number of leaf nodes (valid numbers) is at most `9 * 2^(n-1)`. The total number of nodes in the recursion tree gives the complexity.
Space
O(n + N), where N is the number of results. The O(n) part comes from the depth of the recursion stack. The O(N) part is for storing the results list. This is more space-efficient than the BFS approach's O(2^n) auxiliary space.
Trade-offs
Pros
Highly efficient for the given constraints.
Elegant and concise recursive solution.
More space-efficient than the iterative BFS approach in terms of auxiliary memory.
Cons
Recursive solutions might lead to stack overflow for very large
n, but this is not a concern with the given constraint ofn <= 9.
Solutions
Solution
class Solution {public int[] numsSameConsecDiff(int n, int k) { List<Integer> res = new ArrayList<>(); for (int i = 1; i < 10; ++i) { dfs(n - 1, k, i, res); } int[] ans = new int[res.size()]; for (int i = 0; i < res.size(); ++i) { ans[i] = res.get(i); } return ans; }private void dfs(int n, int k, int t, List<Integer> res) { if (n == 0) { res.add(t); return; } int last = t % 10; if (last + k <= 9) { dfs(n - 1, k, t * 10 + last + k, res); } if (last - k >= 0 && k != 0) { dfs(n - 1, k, t * 10 + last - k, res); } }}function numsSameConsecDiff ( n , k ) { const ans = new Set (); const boundary = 10 ** ( n - 1 ); const dfs = nums => { if ( nums >= boundary ) { ans . add ( nums ); return ; } const num = nums % 10 ; for ( const x of [ num + k , num - k ]) { if ( 0 <= x && x < 10 ) { dfs ( nums * 10 + x ); } } }; for ( let i = 1 ; i < 10 ; i ++ ) { dfs ( i ); } return [... ans ]; }class Solution {public: vector<int> ans; vector<int> numsSameConsecDiff(int n, int k) { for (int i = 1; i < 10; ++i) dfs(n - 1, k, i); return ans; } void dfs(int n, int k, int t) { if (n == 0) { ans.push_back(t); return; } int last = t % 10; if (last + k <= 9) dfs(n - 1, k, t * 10 + last + k); if (last - k >= 0 && k != 0) dfs(n - 1, k, t * 10 + last - k); }};class Solution: def numsSameConsecDiff(self, n: int, k: int) -> List[int]: ans = [] def dfs(n, k, t): if n == 0: ans . append(t) return last = t % 10 if last + k <= 9: dfs(n - 1, k, t * 10 + last + k) if last - k >= 0 and k != 0: dfs(n - 1, k, t * 10 + last - k) for i in range(1, 10): dfs(n - 1, k, i) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.