# LeetCode 967: Numbers With Same Consecutive Differences

## Problem Restatement

We are given two integers:

```python
n
k
```

Return all integers with exactly `n` digits such that the absolute difference between every two consecutive digits is exactly `k`.

Numbers must not have leading zeros.

The answer may be returned in any order.

The official constraints are:

| Constraint | Value |
|---|---|
| `n` | `2 <= n <= 9` |
| `k` | `0 <= k <= 9` |

Source: LeetCode problem statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n`, the required number length |
| Input | Integer `k`, the required adjacent digit difference |
| Output | All valid `n`-digit integers |
| Rule | `abs(digit[i] - digit[i + 1]) == k` |

Example function shape:

```python
def numsSameConsecDiff(n: int, k: int) -> list[int]:
    ...
```

## Examples

Example 1:

```python
n = 3
k = 7
```

Output:

```python
[181, 292, 707, 818, 929]
```

Explanation:

```python
181 -> |1 - 8| = 7 and |8 - 1| = 7
292 -> |2 - 9| = 7 and |9 - 2| = 7
707 -> |7 - 0| = 7 and |0 - 7| = 7
818 -> |8 - 1| = 7 and |1 - 8| = 7
929 -> |9 - 2| = 7 and |2 - 9| = 7
```

The number `070` is invalid because it has a leading zero.

Example 2:

```python
n = 2
k = 1
```

Output:

```python
[10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98]
```

## First Thought: Generate All n-Digit Numbers

One direct approach is to try every number from:

```python
10 ** (n - 1)
```

to:

```python
10 ** n - 1
```

Then check whether every adjacent digit difference is `k`.

This is too much work. For `n = 9`, there are hundreds of millions of numbers.

We should generate only valid candidates.

## Key Insight

Build numbers digit by digit.

If the current last digit is `d`, then the next digit can only be:

```python
d + k
```

or:

```python
d - k
```

as long as the digit stays between `0` and `9`.

The first digit cannot be `0`, so we start from digits `1` through `9`.

## Handling k = 0

When `k = 0`, both choices are the same:

```python
d + 0 = d
d - 0 = d
```

If we blindly try both, we generate duplicate numbers.

So for each step, we should collect next digits in a set:

```python
next_digits = {last + k, last - k}
```

Then we try each valid digit from that set.

## Algorithm

Use DFS.

Start with every first digit from `1` to `9`.

For each partial number:

1. If its length is `n`, add it to the answer.
2. Otherwise, get its last digit.
3. Try `last + k` and `last - k`.
4. If the next digit is between `0` and `9`, append it and continue.

To append a digit to an integer:

```python
new_number = current_number * 10 + next_digit
```

## Correctness

The algorithm starts only with digits `1` through `9`, so every generated number has no leading zero.

At every step, the algorithm appends only digits whose absolute difference from the previous digit is exactly `k`. Therefore, every generated complete number satisfies the required adjacent-difference rule.

Now consider any valid answer. Its first digit must be from `1` through `9`, so the algorithm starts with that digit. For each later digit, the valid number must use either previous digit plus `k` or previous digit minus `k`. The algorithm tries both valid possibilities at every step, so it will follow the exact digit sequence of this answer.

Thus, every valid number is generated, and every generated number is valid. Therefore, the algorithm returns exactly the required set of numbers.

## Complexity

At each position, there are at most two next choices.

| Metric | Value | Why |
|---|---|---|
| Time | `O(9 * 2^(n - 1))` | Each digit path branches at most twice |
| Space | `O(9 * 2^(n - 1))` | The answer list can contain that many numbers |

The recursion depth is `O(n)`.

Since `n <= 9`, this is small.

## Implementation

```python
class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> list[int]:
        answer = []

        def dfs(length: int, number: int) -> None:
            if length == n:
                answer.append(number)
                return

            last_digit = number % 10

            for next_digit in {last_digit + k, last_digit - k}:
                if 0 <= next_digit <= 9:
                    dfs(length + 1, number * 10 + next_digit)

        for first_digit in range(1, 10):
            dfs(1, first_digit)

        return answer
```

## Code Explanation

We store valid complete numbers here:

```python
answer = []
```

The DFS state is:

```python
dfs(length, number)
```

where `length` is the number of digits already built.

If we have built `n` digits:

```python
if length == n:
    answer.append(number)
    return
```

we add the number to the result.

Otherwise, we inspect the last digit:

```python
last_digit = number % 10
```

The only possible next digits are:

```python
last_digit + k
last_digit - k
```

Using a set removes duplicates when `k = 0`:

```python
for next_digit in {last_digit + k, last_digit - k}:
```

If the next digit is valid:

```python
if 0 <= next_digit <= 9:
```

we append it:

```python
dfs(length + 1, number * 10 + next_digit)
```

We start from `1` through `9`:

```python
for first_digit in range(1, 10):
```

because leading zeros are not allowed.

## Testing

Because the answer may be returned in any order, compare sorted lists.

```python
def run_tests():
    s = Solution()

    assert sorted(s.numsSameConsecDiff(3, 7)) == [181, 292, 707, 818, 929]

    assert sorted(s.numsSameConsecDiff(2, 1)) == [
        10, 12,
        21, 23,
        32, 34,
        43, 45,
        54, 56,
        65, 67,
        76, 78,
        87, 89,
        98,
    ]

    assert sorted(s.numsSameConsecDiff(2, 0)) == [
        11, 22, 33, 44, 55, 66, 77, 88, 99,
    ]

    assert sorted(s.numsSameConsecDiff(3, 0)) == [
        111, 222, 333, 444, 555, 666, 777, 888, 999,
    ]

    assert sorted(s.numsSameConsecDiff(2, 9)) == [90]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `(3, 7)` | Main example |
| `(2, 1)` | Many two-digit outputs |
| `(2, 0)` | Checks duplicate prevention |
| `(3, 0)` | Same digit repeated |
| `(2, 9)` | Only `90` is valid |