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.
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); } }}Video 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.