Numbers With Same Consecutive Differences

Medium Recursion & Backtracking Digit-by-Digit Construction Original on LeetCode

Reported atFlipkart

Numbers With Same Consecutive Differences is a medium recursion & backtracking problem solved with the digit-by-digit construction pattern. The best approach, optimal (dfs digit by digit), runs in O(9 · 2^(n-1) · n) time and O(n) recursion space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan every n-digit number) up.

Problem

Given two integers n and k, return every non-negative integer that has exactly n digits and in which every pair of neighbouring digits differs by exactly k (absolute difference).

The numbers must not have leading zeros, so a value like 07 is not a valid 2-digit number. You may return the answer in any order.

Examples

Example 1

Input
n = 3, k = 5
Output
[161, 272, 383, 494, 505, 616, 727, 838, 949]
Why
From each first digit only one next digit is 5 away (the other choice leaves 0–9), so the pattern bounces back and forth.

Example 2

Input
n = 2, k = 8
Output
[19, 80, 91]
Why
Only the pairs (1, 9), (8, 0) and (9, 1) differ by 8 with a non-zero first digit.

Example 3

Input
n = 2, k = 0
Output
[11, 22, 33, 44, 55, 66, 77, 88, 99]
Why
With k = 0 every digit repeats; 00 is excluded because of the leading zero.

Constraints

  • 2 <= n <= 9
  • 0 <= k <= 9
  • Return the numbers in any order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan every n-digit number)O(10^n · n)O(1) extra
Optimal (DFS digit by digit)O(9 · 2^(n-1) · n)O(n) recursion

1Brute force (scan every n-digit number)

TimeO(10^n · n)There are 9 · 10^(n-1) candidates and each takes n digit steps to check.
SpaceO(1) extraOnly a few counters besides the output list.

Loop over every number from 10^(n-1) to 10^n - 1 and keep those whose adjacent digits all differ by exactly k.

  1. For each x in [10^(n-1), 10^n): peel digits from the right and compare each pair of neighbours.
  2. Keep x if every neighbouring difference equals k.
class Solution {
    public List<Integer> numsSameConsecDiff(int n, int k) {
        List<Integer> res = new ArrayList<>();
        int lo = (int) Math.pow(10, n - 1), hi = lo * 10;
        for (int x = lo; x < hi; x++) if (ok(x, k)) res.add(x);
        return res;
    }

    private boolean ok(int x, int k) {
        int prev = x % 10;
        x /= 10;
        while (x > 0) {
            int d = x % 10;
            if (Math.abs(d - prev) != k) return false;
            prev = d;
            x /= 10;
        }
        return true;
    }
}

2Optimal (DFS digit by digit)

TimeO(9 · 2^(n-1) · n)Each digit branches at most twice, so at most 9 · 2^(n-1) numbers are built, each in n steps.
SpaceO(n) recursionRecursion depth is n (the output list itself is not counted).

Grow valid numbers directly. A prefix ending in digit d can only continue with d + k or d - k (when inside 0–9), so no invalid number is ever built. Start from each non-zero first digit.

  1. For first digit 1..9 call dfs(num = digit, len = 1).
  2. dfs: if len == n, record num and return.
  3. Let d = num % 10. If d + k <= 9, recurse on num * 10 + d + k.
  4. If k > 0 and d - k >= 0, recurse on num * 10 + d - k (skip when k = 0 to avoid a duplicate).
class Solution {
    public List<Integer> numsSameConsecDiff(int n, int k) {
        List<Integer> res = new ArrayList<>();
        for (int d = 1; d <= 9; d++) dfs(d, 1, n, k, res);
        return res;
    }

    private void dfs(int num, int len, int n, int k, List<Integer> res) {
        if (len == n) { res.add(num); return; }
        int last = num % 10;
        if (last + k <= 9) dfs(num * 10 + last + k, len + 1, n, k, res);
        if (k > 0 && last - k >= 0) dfs(num * 10 + last - k, len + 1, n, k, res);
    }
}

Edge cases to test

  • k = 0: the two candidate next digits coincide; add it once, not twice
  • Leading zeros are not allowed, but a 0 inside the number is fine (e.g. 505)
  • k = 9: only 9 → 0 and 0 → 9 jumps exist
  • Large n with small k: the answer list grows like 2^n

Hints

Hint 1

Checking every n-digit number works for small n, but there are 9 · 10^(n-1) of them.

Hint 2

Build the number one digit at a time. Given the last digit d, the next digit can only be d + k or d - k.

Hint 3

Start from each first digit 1–9 and DFS (or BFS by length). Watch out for k = 0, where both choices are the same digit.

FAQ

What is the best time complexity for Numbers With Same Consecutive Differences?

Optimal (DFS digit by digit) runs in O(9 · 2^(n-1) · n) time and O(n) recursion extra space. Each digit branches at most twice, so at most 9 · 2^(n-1) numbers are built, each in n steps.

Which pattern does Numbers With Same Consecutive Differences use?

It is a recursion & backtracking problem that uses the digit-by-digit construction pattern.

Is there a brute force solution for Numbers With Same Consecutive Differences?

Yes. Brute force (scan every n-digit number) takes O(10^n · n) time and O(1) extra space. Loop over every number from 10^(n-1) to 10^n - 1 and keep those whose adjacent digits all differ by exactly k.

Which edge cases should I test for Numbers With Same Consecutive Differences?

k = 0: the two candidate next digits coincide; add it once, not twice; Leading zeros are not allowed, but a 0 inside the number is fine (e.g. 505); k = 9: only 9 → 0 and 0 → 9 jumps exist; Large n with small k: the answer list grows like 2^n.