Numbers With Same Consecutive Differences

Numbers With Same Consecutive Differences - Problem

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: The integers should not have leading zeros. Integers as 02 and 043 are not allowed.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, k = 7

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

💡 Note: For 3-digit numbers with consecutive difference 7: 181 (|8-1|=7, |1-8|=7), 292 (|9-2|=7, |2-9|=7), etc.

Example 2 — Single Digit

$ Input: n = 1, k = 3

› Output: [0,1,2,3,4,5,6,7,8,9]

💡 Note: For single digits, all digits 0-9 are valid since there are no consecutive pairs to check.

Example 3 — Small Difference

$ Input: n = 2, k = 1

› Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

💡 Note: 2-digit numbers where consecutive digits differ by 1: 10 (|1-0|=1), 12 (|1-2|=1), etc.

Constraints

1 ≤ n ≤ 8
0 ≤ k ≤ 9

Visualization

Tap to expand

Key Insight: Each digit has at most 2 valid next digits (±k)

Understanding the Visualization

Input

Given n=3 (length) and k=7 (difference)

Process

Build numbers where |digit[i+1] - digit[i]| = k

Output

All valid n-digit numbers

Key Takeaway

🎯 Key Insight: Each digit constrains the next digit to exactly two possibilities: current ± k

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is that each digit constrains the next digit to at most two possibilities: current digit ± k. We can use backtracking or BFS to build valid numbers digit by digit, avoiding the need to check all possible n-digit numbers. Best approach is BFS with Time: O(2^n), Space: O(2^n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Numbers	O(10^n)	O(1)	Generate all possible n-digit numbers and filter valid ones
BFS - Level by Level Construction	O(2^n)	O(2^n)	Use BFS to build numbers level by level, each level adds one digit
Backtracking - Build Valid Numbers	O(2^n)	O(n)	Build numbers digit by digit, backtrack when invalid

Brute Force - Generate All Numbers — Algorithm Steps

Generate all n-digit numbers
For each number, check consecutive digit differences
Keep numbers where all differences equal k

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Range

Create all numbers from 10^(n-1) to 10^n - 1

Check Each

For each number, verify consecutive digit differences

Filter Valid

Keep only numbers where all differences equal k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int* solution(int n, int k, int* returnSize) {
    if (n == 1) {
        int* result = (int*)malloc(10 * sizeof(int));
        for (int i = 0; i < 10; i++) {
            result[i] = i;
        }
        *returnSize = 10;
        return result;
    }
    
    int* result = (int*)malloc(1000 * sizeof(int));
    int count = 0;
    int start = (int)pow(10, n - 1);
    int end = (int)pow(10, n);
    
    for (int num = start; num < end; num++) {
        char numStr[20];
        sprintf(numStr, "%d", num);
        int valid = 1;
        
        for (int i = 1; i < strlen(numStr); i++) {
            int curr = numStr[i] - '0';
            int prev = numStr[i-1] - '0';
            if (abs(curr - prev) != k) {
                valid = 0;
                break;
            }
        }
        
        if (valid) {
            result[count++] = num;
        }
    }
    
    *returnSize = count;
    return result;
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(n, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(10^n)

Must check all 9×10^(n-1) possible n-digit numbers

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for checking

✓ Linear Space

35.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Numbers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler