967. Numbers With Same Consecutive Differences LeetCode Solution
In this guide, you will get 967. Numbers With Same Consecutive Differences LeetCode Solution with the best time and space complexity. The solution to Numbers With Same Consecutive Differences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 <= 9
0 <= k <= 9
Complexity Analysis
Time Complexity: O(n \cdot 2^n)
Space Complexity: O(2^n)
967. Numbers With Same Consecutive Differences LeetCode Solution in C++
class Solution {
public:
vector<int> numsSameConsecDiff(int n, int k) {
if (n == 1)
return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<int> ans;
if (k == 0) {
for (char c = '1'; c <= '9'; ++c)
ans.push_back(stoi(string(n, c)));
return ans;
}
for (int num = 1; num <= 9; ++num)
dfs(n - 1, k, num, ans);
return ans;
}
private:
void dfs(int n, int k, int num, vector<int>& ans) {
if (n == 0) {
ans.push_back(num);
return;
}
const int lastDigit = num % 10;
for (const int nextDigit : {lastDigit - k, lastDigit + k})
if (0 <= nextDigit && nextDigit <= 9)
dfs(n - 1, k, num * 10 + nextDigit, ans);
}
}; /* code provided by PROGIEZ */
967. Numbers With Same Consecutive Differences LeetCode Solution in Java
class Solution {
public int[] numsSameConsecDiff(int n, int k) {
if (n == 1)
return new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
List<Integer> ans = new ArrayList<>();
if (k == 0) {
for (char c = '1'; c <= '9'; ++c) {
final String s = String.valueOf(c).repeat(n);
ans.add(Integer.parseInt(s));
}
return ans.stream().mapToInt(Integer::intValue).toArray();
}
for (int num = 1; num <= 9; ++num)
dfs(n - 1, k, num, ans);
return ans.stream().mapToInt(Integer::intValue).toArray();
}
private void dfs(int n, int k, int num, List<Integer> ans) {
if (n == 0) {
ans.add(num);
return;
}
final int lastDigit = num % 10;
for (final int nextDigit : new int[] {lastDigit - k, lastDigit + k})
if (0 <= nextDigit && nextDigit <= 9)
dfs(n - 1, k, num * 10 + nextDigit, ans);
}
} // code provided by PROGIEZ
967. Numbers With Same Consecutive Differences LeetCode Solution in Python
