Count Numbers with Non-Decreasing Digits - Practice Coding Problems

Count Numbers with Non-Decreasing Digits - Problem

You are given two integers, l and r, represented as strings, and an integer b. Return the count of integers in the inclusive range [l, r] whose digits are in non-decreasing order when represented in base b.

An integer is considered to have non-decreasing digits if, when read from left to right (from the most significant digit to the least significant digit), each digit is greater than or equal to the previous one.

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

Input & Output

Example 1 — Basic Range in Base 10

$ Input: l = "12", r = "15", b = 10

› Output: 3

💡 Note: Numbers 12, 13, 15 have non-decreasing digits. 14 is invalid because 4 < 1.

Example 2 — Small Range in Base 2

$ Input: l = "1", r = "5", b = 2

› Output: 4

💡 Note: In base 2: 1→1, 2→10, 3→11, 4→100, 5→101. Valid: 1, 11, 100, 101 (count = 4)

Example 3 — Single Number

$ Input: l = "123", r = "123", b = 10

› Output: 1

💡 Note: Only number 123 in range, digits 1≤2≤3 so it's valid

Constraints

1 ≤ l ≤ r ≤ 10¹⁸
2 ≤ b ≤ 10
l and r are given as strings

Visualization

Tap to expand

Understanding the Visualization

Input Range

Given range [12, 15] in base 10

Check Digits

Verify each number has non-decreasing digits

Count Valid

Return count of valid numbers

Key Takeaway

🎯 Key Insight: Use digit DP to count valid numbers efficiently without checking each one individually

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use digit dynamic programming instead of checking each number individually. We build valid numbers digit by digit while maintaining the non-decreasing constraint. Best approach is memoized digit DP with time O(d × b²) and space O(d × b), where d is number of digits and b is the base.

Common Approaches

Approach	Time	Space	Notes
✓ Digit Dynamic Programming	O(d × b²)	O(d × b)	Use memoized recursion to count valid numbers without generating all
Brute Force - Check Every Number	O((r-l) × log_b(r))	O(log_b(r))	Convert each number to base b and check if digits are non-decreasing

Digit Dynamic Programming — Algorithm Steps

Use digit DP with states: position, previous digit, tight constraint
For each position, try digits >= previous digit
Use memoization to avoid recomputing same states
Handle boundary conditions carefully

Visualization

Tap to expand

Step-by-Step Walkthrough

States

Track position, previous digit, bounds

Transitions

Choose next digit >= previous

Memoize

Cache results for efficiency

Code -

solution.c — C

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

const int MOD = 1000000007;

typedef struct {
    int pos, prevDigit;
    int tight, started;
    long long result;
} CacheEntry;

CacheEntry cache[1000];
int cacheSize = 0;

void getDigits(long long num, int base, int* digits, int* len) {
    *len = 0;
    if (num == 0) {
        digits[0] = 0;
        *len = 1;
        return;
    }
    
    int temp[64];
    int tempLen = 0;
    while (num > 0) {
        temp[tempLen++] = num % base;
        num /= base;
    }
    
    for (int i = 0; i < tempLen; i++) {
        digits[i] = temp[tempLen - 1 - i];
    }
    *len = tempLen;
}

long long findInCache(int pos, int prevDigit, int tight, int started) {
    for (int i = 0; i < cacheSize; i++) {
        if (cache[i].pos == pos && cache[i].prevDigit == prevDigit &&
            cache[i].tight == tight && cache[i].started == started) {
            return cache[i].result;
        }
    }
    return -1;
}

void addToCache(int pos, int prevDigit, int tight, int started, long long result) {
    if (cacheSize < 1000) {
        cache[cacheSize].pos = pos;
        cache[cacheSize].prevDigit = prevDigit;
        cache[cacheSize].tight = tight;
        cache[cacheSize].started = started;
        cache[cacheSize].result = result;
        cacheSize++;
    }
}

long long dp(int pos, int prevDigit, int tight, int started, int* digits, int digitsLen, int b) {
    if (pos == digitsLen) {
        return started ? 1 : 0;
    }
    
    long long cached = findInCache(pos, prevDigit, tight, started);
    if (cached != -1) {
        return cached;
    }
    
    int limit = tight ? digits[pos] : b - 1;
    long long result = 0;
    
    for (int digit = 0; digit <= limit; digit++) {
        int newTight = tight && (digit == limit);
        int newStarted = started || (digit > 0);
        
        if (!newStarted || digit >= prevDigit) {
            int nextPrev = newStarted ? digit : -1;
            result += dp(pos + 1, nextPrev, newTight, newStarted, digits, digitsLen, b);
            result %= MOD;
        }
    }
    
    addToCache(pos, prevDigit, tight, started, result);
    return result;
}

long long countValid(char* numStr, int b) {
    long long num = atoll(numStr);
    if (num == 0) return 1;
    
    int digits[64], digitsLen;
    getDigits(num, b, digits, &digitsLen);
    
    cacheSize = 0;
    return dp(0, -1, 1, 0, digits, digitsLen, b);
}

void subtractOne(char* numStr, char* result) {
    long long num = atoll(numStr);
    if (num <= 0) {
        strcpy(result, "0");
    } else {
        sprintf(result, "%lld", num - 1);
    }
}

int solution(char* l, char* r, int b) {
    long long countR = countValid(r, b);
    char lMinus1[100];
    subtractOne(l, lMinus1);
    long long countLMinus1 = countValid(lMinus1, b);
    return (countR - countLMinus1 + MOD) % MOD;
}

int main() {
    char l[100], r[100];
    int b;
    
    fgets(l, sizeof(l), stdin);
    fgets(r, sizeof(r), stdin);
    scanf("%d", &b);
    
    l[strcspn(l, "\n")] = 0;
    r[strcspn(r, "\n")] = 0;
    
    int result = solution(l, r, b);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(d × b²)

d digits, b possible values per digit, b previous digit states

✓ Linear Growth

Space Complexity

O(d × b)

Memoization table stores states for d positions and b previous digits

✓ Linear Space

28.0K Views

Medium Frequency

~35 min Avg. Time

850 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

Digit Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler