Numbers With Same Consecutive Differences

Medium
1583.

Numbers With Same Consecutive Differences

Numbers With Same Consecutive Differences is a medium coding problem on breadth-first search and backtracking, asked in Amazon and Flipkart interviews.

Return every n-digit positive integer in which any two neighbouring digits differ by exactly k (in absolute value). Numbers may not have leading zeros, so the first digit is between 1 and 9 — but later digits may be 0.

Return the numbers in ascending order.

Example 1

Input
n = 3, k = 7
Output
[181,292,707,818,929]

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]

Example 3

Input
n = 2, k = 0
Output
[11,22,33,44,55,66,77,88,99]
Explanation
With k = 0 every digit repeats the first; each number appears once.

Constraints

  • 2 <= n <= 9
  • 0 <= k <= 9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Numbers With Same Consecutive Differences — Solution

Numbers With Same Consecutive Differences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Numbers With Same Consecutive Differences is a medium coding problem on breadth-first search and backtracking, asked in Amazon and Flipkart interviews.

Problem statement

Return every n-digit positive integer in which any two neighbouring digits differ by exactly k (in absolute value). Numbers may not have leading zeros, so the first digit is between 1 and 9 — but later digits may be 0.

Return the numbers in ascending order.

Example 1

Input: n = 3, k = 7
Output: [181,292,707,818,929]

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]

Example 3

Input: n = 2, k = 0
Output: [11,22,33,44,55,66,77,88,99]
Explanation: With k = 0 every digit repeats the first; each number appears once.

Constraints

  • 2 <= n <= 9
  • 0 <= k <= 9

Hints for Numbers With Same Consecutive Differences

  1. Hint 1

    Build the numbers digit by digit: after a digit d, the next digit can only be d - k or d + k, if it stays between 0 and 9.

  2. Hint 2

    Start from each first digit 1..9 and extend depth-first (or level by level) until the number has n digits.

  3. Hint 3

    When k = 0, d - k and d + k are the same digit — take it once, or you will list numbers twice.

How to solve Numbers With Same Consecutive Differences

Every valid number is a walk of length n on the digits where each step moves by ±k. Enumerate the walks from each non-zero first digit.

Approach

  1. For each first digit f from 1 to 9, run dfs(f, 1).
  2. dfs(num, len): if len == n, record num. Otherwise let d = num % 10 and recurse on num * 10 + (d - k) when d - k >= 0, then on num * 10 + (d + k) when k > 0 and d + k <= 9.
  3. Because every number has the same length, trying smaller digits first at every position produces them in ascending order.

Why it works

Each number is determined by its digits, and each digit after the first is forced to be one of at most two values, so the search lists every valid number exactly once (the k > 0 test stops the duplicate branch when the two candidates coincide).

Complexity

  • Time — O(9 · 2^(n-1)) numbers at most
  • Space — O(n) recursion depth besides the output

Pitfalls

  • The first digit cannot be 0, but later digits can.
  • k = 0 makes both candidates equal; branching twice duplicates every number.
  • The largest value, 989898989, still fits in a 32-bit int.

Reference solution

Python

from typing import List

def numsSameConsecDiff(n: int, k: int) -> List[int]:
    out = []

    def dfs(num, length):
        if length == n:
            out.append(num)
            return
        d = num % 10
        if d - k >= 0:
            dfs(num * 10 + d - k, length + 1)
        if k > 0 and d + k <= 9:
            dfs(num * 10 + d + k, length + 1)

    for f in range(1, 10):
        dfs(f, 1)
    return out

Java

public static int[] numsSameConsecDiff(int n, int k) {
    List<Integer> out = new ArrayList<>();
    for (int f = 1; f <= 9; f++) consecDfs(f, 1, n, k, out);
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

static void consecDfs(int num, int len, int n, int k, List<Integer> out) {
    if (len == n) {
        out.add(num);
        return;
    }
    int d = num % 10;
    if (d - k >= 0) consecDfs(num * 10 + d - k, len + 1, n, k, out);
    if (k > 0 && d + k <= 9) consecDfs(num * 10 + d + k, len + 1, n, k, out);
}

C++

void consecDfs(int num, int len, int n, int k, vector<int>& out) {
    if (len == n) {
        out.push_back(num);
        return;
    }
    int d = num % 10;
    if (d - k >= 0) consecDfs(num * 10 + d - k, len + 1, n, k, out);
    if (k > 0 && d + k <= 9) consecDfs(num * 10 + d + k, len + 1, n, k, out);
}

vector<int> numsSameConsecDiff(int n, int k) {
    vector<int> out;
    for (int f = 1; f <= 9; f++) consecDfs(f, 1, n, k, out);
    return out;
}

JavaScript

var numsSameConsecDiff = function(n, k) {
    var out = [];
    var dfs = function(num, len) {
        if (len === n) {
            out.push(num);
            return;
        }
        var d = num % 10;
        if (d - k >= 0) dfs(num * 10 + d - k, len + 1);
        if (k > 0 && d + k <= 9) dfs(num * 10 + d + k, len + 1);
    };
    for (var f = 1; f <= 9; f++) dfs(f, 1);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Backtracking