Skip to main content

967. Numbers With Same Consecutive Differences

medium

Return all n-digit numbers where every pair of consecutive digits differs by exactly k. DFS builds digits one at a time — at each step you have at most two choices: last digit + k or last digit - k.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k. Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid. You may return the answer in any order.

Constraints

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

Examples

Example 1

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

Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

DFS from each starting digit 1..9 (no leading zero).

Hint 2

At each step, lastDigit + k or lastDigit - k — whichever is in 0..9 — is the next digit.

Hint 3

When k == 0, the two choices collapse into one — don't double-count.

Hint 4

Base case: built n digits -> append to result.

Solution approach

Reveal approach

DFS with (currentNumber, digitsRemaining). Start: for d in 1..9, dfs(d, n - 1). dfs(cur, remaining): if remaining == 0, append cur to result and return. lastDigit = cur % 10. For next in [lastDigit + k, lastDigit - k]: if next is in 0..9, dfs(cur * 10 + next, remaining - 1). When k == 0, the two next values are equal — guard with a Set or short-circuit. Time and space are bounded by the answer size, which is at most 9 * 2^(n - 1) — small even for n = 9. The algorithm is essentially a constrained 10-ary tree traversal pruned by the consecutive-difference rule.

Complexity

Time
O(9 * 2^(n - 1))
Space
O(n)

Related patterns

  • recursion
  • dfs
  • constrained-enumeration

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Numbers With Same Consecutive Differences and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →