Count Stepping Numbers in Range - Practice Coding Problems

Count Stepping Numbers in Range - Problem

Given two positive integers low and high represented as strings, find the count of stepping numbers in the inclusive range [low, high].

A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.

Return an integer denoting the count of stepping numbers in the inclusive range [low, high].

Since the answer may be very large, return it modulo 10⁹ + 7.

Note: A stepping number should not have a leading zero.

Input & Output

Example 1 — Basic Range

$ Input: low = "0", high = "21"

› Output: 13

💡 Note: Stepping numbers in [0,21]: 0,1,2,3,4,5,6,7,8,9,10,12,21. Count = 13

Example 2 — Single Digit Range

$ Input: low = "1", high = "9"

› Output: 9

💡 Note: All single digits 1-9 are stepping numbers. Count = 9

Example 3 — Larger Range

$ Input: low = "10", high = "15"

› Output: 2

💡 Note: Stepping numbers in [10,15]: 10,12. Count = 2

Constraints

1 ≤ low.length, high.length ≤ 15
low and high consist of only digits
low ≤ high
low and high don't have leading zeros

Visualization

Tap to expand

Understanding the Visualization

Range

Given range [low, high] as strings

Check

Find numbers where |digit[i] - digit[i+1]| = 1

Count

Return count modulo 10^9 + 7

Key Takeaway

🎯 Key Insight: Use digit DP to efficiently count stepping numbers without generating all of them

Asked in

G Google 45 f Meta 38 a Amazon 32

The key insight is to use digit DP to count stepping numbers efficiently without generating them all. A stepping number has adjacent digits differing by exactly 1. Best approach uses memoized digit DP with states (position, last_digit, tight, started). Time: O(d × 10), Space: O(d × 10).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Number	O(n × d)	O(1)	Check each number in the range to see if it's a stepping number
Digit DP with Memoization	O(d × 10 × 2 × 2)	O(d × 10 × 2 × 2)	Use digit DP to count stepping numbers efficiently

Brute Force - Check Every Number — Algorithm Steps

Convert low and high strings to integers
For each number in range, check if it's stepping
Count valid stepping numbers

Visualization

Tap to expand

Step-by-Step Walkthrough

Range

Check numbers from low to high

Validate

Check if each number is stepping

Count

Count valid stepping numbers

Code -

solution.c — C

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

#define MOD 1000000007

int isStepping(long long num) {
    char s[20];
    sprintf(s, "%lld", num);
    int len = strlen(s);
    if (len == 1) return 1;
    for (int i = 0; i < len - 1; i++) {
        if (abs(s[i] - s[i + 1]) != 1) {
            return 0;
        }
    }
    return 1;
}

int solution(char* low, char* high) {
    long long lowNum = atoll(low);
    long long highNum = atoll(high);
    long long count = 0;
    
    for (long long num = lowNum; num <= highNum; num++) {
        if (isStepping(num)) {
            count = (count + 1) % MOD;
        }
    }
    
    return (int)count;
}

int main() {
    char low[20], high[20];
    fgets(low, sizeof(low), stdin);
    fgets(high, sizeof(high), stdin);
    low[strcspn(low, "\n")] = 0;
    high[strcspn(high, "\n")] = 0;
    printf("%d\n", solution(low, high));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × d)

Where n is the range size and d is average digits per number

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

23.4K Views

Medium Frequency

~35 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 - Check Every Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler