LeetCode 967: Numbers With Same Consecutive Differences

Problem Restatement

We are given two integers:

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:

Source: LeetCode problem statement.

Input and Output

Example function shape:

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

Examples

Example 1:

n = 3
k = 7

Output:

[181, 292, 707, 818, 929]

Explanation:

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:

n = 2
k = 1

Output:

[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:

10 ** (n - 1)

to:

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:

d + k

or:

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:

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:

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:

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.

The recursion depth is O(n).

Since n <= 9, this is small.

Implementation

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:

answer = []

The DFS state is:

dfs(length, number)

where length is the number of digits already built.

If we have built n digits:

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

we add the number to the result.

Otherwise, we inspect the last digit:

last_digit = number % 10

The only possible next digits are:

last_digit + k
last_digit - k

Using a set removes duplicates when k = 0:

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

If the next digit is valid:

if 0 <= next_digit <= 9:

we append it:

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

We start from 1 through 9:

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.

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: