# Numbers With Same Consecutive Differences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/numbers-with-same-consecutive-differences)
Canonical: https://scaleengineer.com/dsa/problems/numbers-with-same-consecutive-differences
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
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`

# Approaches
## Brute Force with Filtering
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`.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Calculate the range of n-digit numbers: `start = 10^(n-1)` and `end = 10^n - 1`.
- Iterate through each number `num` from `start` to `end`.
- For each `num`, create a helper function `isValid(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 is `k`.
- 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 `result` list.
- Finally, convert the list to an array and return it.

## Iterative Approach (BFS)
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.
**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)`.
**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.
### Explanation
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`.

```java
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();
    }
}
```
### Algorithm
- Initialize a list or queue, `currentLevel`, with single-digit numbers from 1 to 9.
- Loop `n-1` times, as we already have numbers of length 1.
- In each iteration, create a new empty list `nextLevel`.
- For each number `num` in `currentLevel`:
  - Get the last digit: `lastDigit = num % 10`.
  - Calculate the two possible next digits: `lastDigit + k` and `lastDigit - k`.
  - If a `nextDigit` is valid (between 0 and 9), form a new number `num * 10 + nextDigit` and add it to `nextLevel`.
  - If `k` is 0, the two options are the same, so only add the new number once.
- After iterating through all numbers in `currentLevel`, replace `currentLevel` with `nextLevel`.
- After the loops complete, `currentLevel` will contain all valid n-digit numbers.

## Recursive Backtracking (DFS)
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.
**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.
**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 of `n <= 9`.
### Explanation
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).

```java
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);
            }
        }
    }
}
```
### 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`, add `currentNum` to `results` and 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`, calculate `nextDigit2 = lastDigit - k`. If it's a valid digit, make another recursive call: `dfs(length + 1, currentNum * 10 + nextDigit2)`.
- After the initial calls complete, convert the `results` list to an array.

# Solutions
### Java

```java
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);
    }
  }
}

```

### JavaScript

```javascript
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 ]; }
```

### CPP

```cpp
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);
  }
};

```

### Python

```python
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 ans

```