Skip to main content
Talentd

Numbers With Same Consecutive Differences - Solution & Explanation

MediumBacktrackingBreadth-First Search12 min readAsked at: Amazon, Google, Flipkart +2
Practice this problem

Problem Statement

Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order.

Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

 

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]

 

Constraints:

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

Approach Overview

Problem Overview: Generate all n-digit integers where the absolute difference between every pair of consecutive digits equals k. Leading zeros are not allowed, so every number must start with digits 1–9. The goal is to efficiently construct all valid numbers that satisfy this constraint.

Approach 1: Brute Force Method (O(10^n * n) time, O(1) extra space)

The straightforward strategy checks every possible n-digit number from 10^(n-1) to 10^n - 1. For each number, iterate through its digits and verify that the absolute difference between consecutive digits equals k. If all pairs satisfy the condition, add the number to the result. This approach works but wastes time validating numbers that clearly cannot satisfy the constraint. Because it examines up to 9 * 10^(n-1) numbers and each validation scans up to n digits, the total complexity becomes O(10^n * n). It is useful for understanding the problem but rarely acceptable in interviews due to the exponential search space.

Approach 2: BFS / Backtracking Construction (O(2^n) time, O(2^n) space)

A better strategy constructs valid numbers digit by digit instead of testing every possibility. Start with digits 1–9. For each partial number, look at its last digit d. The next digit must be either d + k or d - k (if those values stay within 0–9). Append the valid digit and continue building the number until the length reaches n. This can be implemented using either backtracking recursion or a queue-based breadth-first search. Each step expands at most two branches, so the search tree stays small compared to brute force. A small optimization avoids duplicating work when k = 0, since both transitions produce the same digit.

Recommended for interviews: The BFS/backtracking construction is the expected solution. It demonstrates that you recognize the constraint structure and generate only valid states rather than filtering invalid ones. Mentioning the brute force approach first shows problem analysis skills, but implementing the constructive search shows stronger algorithmic thinking and familiarity with state expansion techniques.

Approach 1: Approach 1: Brute Force Method

The brute force method involves iterating through all possible solutions to find the correct one. While it might not be the most efficient, it serves as a good starting point to understand the problem.

This solution demonstrates a basic function using the brute force approach in C. Adjust the implementation as per your problem.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Approach 2: Optimized Method using a Data Structure

This approach utilizes an efficient data structure that best fits the problem, reducing time complexity. Choose from hash tables, arrays, or trees based on the requirements.

This solution demonstrates a more optimized function using specific data structures in C. Optimize the implementation based on your problem.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) using auxiliary data structures.

Try this approach in the editor →

Approach 3: DFS

We can enumerate the first digit of all numbers of length n, and then use the depth-first search method to recursively construct all numbers that meet the conditions.

Specifically, we first define a boundary value boundary = 10^{n-1}, which represents the minimum value of the number we need to construct. Then, we enumerate the first digit from 1 to 9. For each digit i, we recursively construct the number of length n with i as the first digit.

The time complexity is (n times 2^n times |\Sigma|), where |\Sigma| represents the set of digits, and in this problem |\Sigma| = 9. The space complexity is O(2^n).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force Method

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2: Optimized Method using a Data Structure

Time Complexity: O(n)
Space Complexity: O(n) using auxiliary data structures.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(10^n * n)O(1)Conceptual baseline or when constraints are extremely small
BFS / Backtracking Digit ConstructionO(2^n)O(2^n)Preferred solution; generates only valid numbers and scales well for typical constraints

Video Solution

Numbers With Same Consecutive Differences | LeetCode 967 | C++, Java, Python • Knowledge Center • 7,359 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Numbers With Same Consecutive Differences easy or hard?
Numbers With Same Consecutive Differences is rated Medium difficulty on LeetCode. The challenge lies in recognizing that you should generate valid numbers directly instead of brute forcing all n-digit numbers.
Numbers With Same Consecutive Differences Python/Java solution
In Python or Java, implement BFS with a queue or recursive backtracking. Start with digits 1–9, compute next digits using lastDigit ± k, and build numbers until length n. Both languages handle the logic cleanly using loops or recursion.
How to solve Numbers With Same Consecutive Differences in O(2^n)?
Start by pushing digits 1 through 9 into a queue or recursion stack. At each step, read the last digit of the current number and compute possible next digits: last + k and last - k. Append valid digits (0–9) and continue until the number reaches length n. Collect every completed number.
What is the best approach for Numbers With Same Consecutive Differences?
The best approach constructs numbers digit by digit using BFS or backtracking. Start with digits 1–9 and repeatedly append digits whose difference from the last digit equals k. This avoids checking invalid numbers and keeps the search limited to valid states, giving about O(2^n) time complexity.
Is Numbers With Same Consecutive Differences asked at Google/Amazon/Meta?
Variations of digit-generation and constrained number construction problems appear in interviews at companies like Google, Amazon, and Meta. The question tests state expansion, recursion, and BFS thinking rather than complex data structures.
What data structure is used in Numbers With Same Consecutive Differences?
Typical implementations use either recursion (backtracking) or a queue for breadth-first search. Both approaches store partially constructed numbers and extend them by appending valid digits based on the difference constraint.
What is the time complexity of Numbers With Same Consecutive Differences?
The optimized BFS/backtracking solution runs in roughly O(2^n) time because each digit can branch into at most two valid next digits (d+k and d-k). Space complexity is also O(2^n) to store generated numbers. A brute force approach would take O(10^n * n) time since it checks every n-digit number.

Ready to solve this problem?

Practice Numbers With Same Consecutive Differences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Letter Combinations of a Phone Number

Next

Generate Parentheses