Numbers With Same Consecutive Differences

medium backtracking dfs recursion

Problem

Given two integers n and k, return all non-negative integers of length n such that the absolute difference between every two consecutive digits is exactly k. The numbers may be returned in any order, and they must not contain leading zeros (except the single number 0 when n is 1).

Inputn = 3, k = 7

Output[181, 292, 707, 818, 929]

For 181: |1 − 8| = 7 and |8 − 1| = 7. Both consecutive gaps equal k.

n (digits)

k (difference)

def nums_same_consec_diff(n, k):
    res = []
    def dfs(num, length):
        if length == n:
            res.append(num)
            return
        last = num % 10
        for nxt in {last + k, last - k}:
            if 0 <= nxt <= 9:
                dfs(num * 10 + nxt, length + 1)
    for first in range(1, 10):
        dfs(first, 1)
    return res

function numsSameConsecDiff(n, k) {
  const res = [];
  function dfs(num, length) {
    if (length === n) { res.push(num); return; }
    const last = num % 10;
    for (const nxt of new Set([last + k, last - k])) {
      if (nxt >= 0 && nxt <= 9) dfs(num * 10 + nxt, length + 1);
    }
  }
  for (let first = 1; first <= 9; first++) dfs(first, 1);
  return res;
}

class Solution {
    private List<Integer> res = new ArrayList<>();
    private int n, k;
    public int[] numsSameConsecDiff(int n, int k) {
        this.n = n; this.k = k;
        for (int first = 1; first <= 9; first++) dfs(first, 1);
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
    private void dfs(int num, int length) {
        if (length == n) { res.add(num); return; }
        int last = num % 10;
        for (int nxt : new int[]{ last + k, last - k }) {
            if (nxt >= 0 && nxt <= 9 && (k != 0 || nxt == last + k))
                dfs(num * 10 + nxt, length + 1);
        }
    }
}

class Solution {
public:
    vector<int> res;
    int n, k;
    vector<int> numsSameConsecDiff(int n, int k) {
        this->n = n; this->k = k;
        for (int first = 1; first <= 9; first++) dfs(first, 1);
        return res;
    }
    void dfs(int num, int length) {
        if (length == n) { res.push_back(num); return; }
        int last = num % 10;
        for (int nxt : {last + k, last - k}) {
            if (nxt >= 0 && nxt <= 9 && (k != 0 || nxt == last + k))
                dfs(num * 10 + nxt, length + 1);
        }
    }
};

Explanation

We grow each number digit by digit with a depth-first search. The current number is carried as an actual integer, and at every step the next digit must be exactly k away from the last digit.

The function dfs(num, length) looks at the last digit with num % 10. From there the only valid next digits are last + k and last - k. We keep one if it lands in 0..9 and recurse with num * 10 + nxt, which appends it. Using a set for {last + k, last - k} avoids trying the same digit twice when k is 0.

To avoid leading zeros, the first digit starts at 1 through 9, which is why the outer loop is for first in range(1, 10). Once length == n, the number has the right number of digits and we record it.

Example: n = 3, k = 7. Starting at 1, the next digit can be 1+7=8 (since 1-7 is negative), then from 8 we can go to 8-7=1, building 181. Other starts give 292, 707, 818, 929.

The search naturally prunes any branch where the next digit leaves the 0..9 range, so only valid numbers reach full length.

Time: O(2ⁿ) Space: O(n)