Numbers With Same Consecutive Differences

Numbers With Same Consecutive Differences

What is this problem about?

The Numbers With Same Consecutive Differences problem asks you to return all n-digit numbers where adjacent digits differ by exactly k. The numbers must not have leading zeros. This coding problem uses BFS or backtracking to build numbers digit by digit. The BFS and backtracking interview pattern is directly applied.

Why is this asked in interviews?

Flipkart, Amazon, and Google ask this to test BFS/DFS number generation with constraints. It validates that candidates can enumerate multi-digit numbers with digit-level constraints systematically without brute-forcing all n-digit numbers. The BFS and backtracking interview pattern is at the core.

Algorithmic pattern used

BFS level-by-level expansion. Initialize queue with digits 1-9 (non-zero first digit). For each number in the queue: take its last digit d. If d+k ≤ 9, add the new number with digit d+k. If k > 0 and d-k ≥ 0, add the number with digit d-k. Expand until numbers have n digits. Special case: n=1 includes 0.

Example explanation

n=2, k=1. Start with 1-9.

• From 1: 12 (1+1=2), 10 (1-1=0). Add [12,10].
• From 2: 23, 21. Add [23,21].
• From 9: 98 (9-1=8). 9+1=10 invalid. Add [98]. Result: [10,12,21,23,32,34,...,98]. Total valid 2-digit numbers with diff=1.

Common mistakes candidates make

• Including leading zeros in numbers with n>1 digits.
• k=0 case: both d+k and d-k equal d — must avoid duplicates (add only once when k=0).
• Generating invalid numbers (digits outside 0-9).
• Not initializing BFS with all valid first digits.

Interview preparation tip

BFS for generating numbers digit by digit is a clean pattern for "all n-digit numbers with property P" problems. The property (consecutive digit difference = k) constrains transitions. Handle k=0 carefully — adding both d+0 and d-0 would duplicate. Practice similar "generate all numbers with digit constraints" problems using BFS or DFS with pruning.