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^9 + 7.

Examples

Example 1

1
2
3
4
5


Input: l = "23", r = "28", b = 8
Output: 3
Explanation:
* The numbers from 23 to 28 in base 8 are: 27, 30, 31, 32, 33, and 34.
* Out of these, 27, 33, and 34 have non-decreasing digits. Hence, the output is 3.

Example 2

1
2
3
4
5


Input: l = "2", r = "7", b = 2
Output: 2
Explanation:
* The numbers from 2 to 7 in base 2 are: 10, 11, 100, 101, 110, and 111.
* Out of these, 11 and 111 have non-decreasing digits. Hence, the output is 2.

Constraints

1 <= l.length <= r.length <= 100
2 <= b <= 10
l and r consist only of digits.
The value represented by l is less than or equal to the value represented by r.
l and r do not contain leading zeros.

Solution

Method 1 – Digit DP (Dynamic Programming on Digits)

Intuition

We use digit dynamic programming (digit DP) to count numbers with non-decreasing digits in a given base up to a certain value. To count in a range [l, r], we count up to r and subtract the count up to l-1.

Approach

Convert the number to a list of digits in base b.
Use a recursive DP function with parameters: position, previous digit, tight (whether the current prefix matches the upper bound), and leading_zero.
For each position, try all possible digits (from prev to the current limit if tight, else b-1).
If not leading_zero, ensure the current digit is at least prev.
Memoize the results for efficiency.
To count in [l, r], compute f(r) - f(l-1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


class Solution {
public:
    int MOD = 1e9+7;
    int dp[25][25][2][2];
    vector<int> digits;
    int b;
    int dfs(int pos, int prev, int tight, int lead) {
        if (pos == digits.size()) return lead ? 0 : 1;
        int &res = dp[pos][prev][tight][lead];
        if (res != -1) return res;
        res = 0;
        int up = tight ? digits[pos] : b-1;
        for (int d = 0; d <= up; ++d) {
            if (!lead && d < prev) continue;
            res = (res + dfs(pos+1, lead && d==0 ? 0 : d, tight && d==up, lead && d==0)) % MOD;
        }
        return res;
    }
    int count(string num, int base) {
        b = base;
        digits.clear();
        for (char c : num) digits.push_back(c-'0');
        reverse(digits.begin(), digits.end());
        vector<int> d2;
        int n = 0;
        for (int i = 0; i < digits.size(); ++i) n = n*10 + digits[i];
        while (n) { d2.push_back(n%b); n /= b; }
        if (d2.empty()) d2.push_back(0);
        reverse(d2.begin(), d2.end());
        digits = d2;
        memset(dp, -1, sizeof dp);
        return dfs(0, 0, 1, 1);
    }
    int countNonDecreasing(string l, string r, int base) {
        auto dec = [](string s) {
            for (int i = s.size()-1; i >= 0; --i) {
                if (s[i] > '0') { s[i]--; break; } s[i] = '9';
            }
            return s;
        };
        int ans = (count(r, base) - count(dec(l), base) + MOD) % MOD;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


func countNonDecreasing(l, r string, b int) int {
    const mod = 1_000_000_007
    var dp [101][11][2][2]int
    var dfs func(pos, prev int, tightL, tightR bool, digitsL, digitsR []int) int
    dfs = func(pos, prev int, tightL, tightR bool, digitsL, digitsR []int) int {
        if pos == len(digitsR) {
            return 1
        }
        if dp[pos][prev][boolToInt(tightL)][boolToInt(tightR)] != -1 {
            return dp[pos][prev][boolToInt(tightL)][boolToInt(tightR)]
        }
        res := 0
        low := 0
        high := b - 1
        if tightL {
            low = digitsL[pos]
        }
        if tightR {
            high = digitsR[pos]
        }
        for d := low; d <= high; d++ {
            if d < prev {
                continue
            }
            res = (res + dfs(pos+1, d, tightL && d == low, tightR && d == high, digitsL, digitsR)) % mod
        }
        dp[pos][prev][boolToInt(tightL)][boolToInt(tightR)] = res
        return res
    }
    // Helper to convert string to digits in base b
    toDigits := func(s string, base int, length int) []int {
        res := make([]int, length)
        num := new(big.Int)
        num.SetString(s, 10)
        for i := length - 1; i >= 0; i-- {
            res[i] = int(new(big.Int).Mod(num, big.NewInt(int64(base))).Int64())
            num.Div(num, big.NewInt(int64(base)))
        }
        return res
    }
    length := len(r)
    digitsL := toDigits(l, b, length)
    digitsR := toDigits(r, b, length)
    for i := range dp {
        for j := range dp[i] {
            for k := range dp[i][j] {
                for m := range dp[i][j][k] {
                    dp[i][j][k][m] = -1
                }
            }
        }
    }
    boolToInt := func(b bool) int {
        if b {
            return 1
        }
        return 0
    }
    return dfs(0, 0, true, true, digitsL, digitsR)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
    static final int MOD = 1_000_000_007;
    int[][][][] dp;
    public int countNonDecreasing(String l, String r, int b) {
        int n = r.length();
        int[] digitsL = toDigits(l, b, n);
        int[] digitsR = toDigits(r, b, n);
        dp = new int[n+1][b+1][2][2];
        for (int[][][] a : dp)
            for (int[][] b1 : a)
                for (int[] b2 : b1)
                    Arrays.fill(b2, -1);
        return dfs(0, 0, 1, 1, digitsL, digitsR, b);
    }
    int dfs(int pos, int prev, int tightL, int tightR, int[] digitsL, int[] digitsR, int base) {
        if (pos == digitsR.length) return 1;
        if (dp[pos][prev][tightL][tightR] != -1) return dp[pos][prev][tightL][tightR];
        int low = tightL == 1 ? digitsL[pos] : 0;
        int high = tightR == 1 ? digitsR[pos] : base - 1;
        int res = 0;
        for (int d = low; d <= high; d++) {
            if (d < prev) continue;
            res = (res + dfs(pos+1, d, tightL & (d == low ? 1 : 0), tightR & (d == high ? 1 : 0), digitsL, digitsR, base)) % MOD;
        }
        return dp[pos][prev][tightL][tightR] = res;
    }
    int[] toDigits(String s, int base, int length) {
        int[] res = new int[length];
        BigInteger num = new BigInteger(s);
        for (int i = length - 1; i >= 0; i--) {
            res[i] = num.mod(BigInteger.valueOf(base)).intValue();
            num = num.divide(BigInteger.valueOf(base));
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
    companion object { const val MOD = 1_000_000_007 }
    lateinit var dp: Array<Array<Array<Array<Int>>>>
    fun countNonDecreasing(l: String, r: String, b: Int): Int {
        val n = r.length
        val digitsL = toDigits(l, b, n)
        val digitsR = toDigits(r, b, n)
        dp = Array(n+1) { Array(b+1) { Array(2) { Array(2) { -1 } } } }
        return dfs(0, 0, 1, 1, digitsL, digitsR, b)
    }
    fun dfs(pos: Int, prev: Int, tightL: Int, tightR: Int, digitsL: IntArray, digitsR: IntArray, base: Int): Int {
        if (pos == digitsR.size) return 1
        if (dp[pos][prev][tightL][tightR] != -1) return dp[pos][prev][tightL][tightR]
        val low = if (tightL == 1) digitsL[pos] else 0
        val high = if (tightR == 1) digitsR[pos] else base - 1
        var res = 0
        for (d in low..high) {
            if (d < prev) continue
            res = (res + dfs(pos+1, d, tightL and if (d == low) 1 else 0, tightR and if (d == high) 1 else 0, digitsL, digitsR, base)) % MOD
        }
        dp[pos][prev][tightL][tightR] = res
        return res
    }
    fun toDigits(s: String, base: Int, length: Int): IntArray {
        val res = IntArray(length)
        var num = s.toBigInteger()
        for (i in length-1 downTo 0) {
            res[i] = (num % base.toBigInteger()).toInt()
            num /= base.toBigInteger()
        }
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution:
    MOD = 10**9 + 7
    def count(self, num: str, base: int) -> int:
        def to_base(n: str, b: int) -> list[int]:
            n = int(n)
            if n == 0: return [0]
            res = []
            while n:
                res.append(n % b)
                n //= b
            return res[::-1]
        from functools import lru_cache
        digits = to_base(num, base)
        n = len(digits)
        @lru_cache(maxsize=None)
        def dp(pos: int, prev: int, tight: bool, lead: bool) -> int:
            if pos == n:
                return 0 if lead else 1
            up = digits[pos] if tight else base-1
            ans = 0
            for d in range(0, up+1):
                if not lead and d < prev: continue
                ans = (ans + dp(pos+1, 0 if lead and d==0 else d, tight and d==up, lead and d==0)) % self.MOD
            return ans
        return dp(0, 0, True, True)
    def countNonDecreasing(self, l: str, r: str, base: int) -> int:
        def dec(s: str) -> str:
            s = list(s)
            i = len(s)-1
            while i >= 0:
                if s[i] > '0':
                    s[i] = str(int(s[i])-1)
                    break
                s[i] = '9'
                i -= 1
            return ''.join(s)
        return (self.count(r, base) - self.count(dec(l), base)) % self.MOD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


use num_bigint::BigInt;
use num_traits::Zero;
impl Solution {
    pub fn count_non_decreasing(l: &str, r: &str, b: usize) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let n = r.len();
        let digits_l = to_digits(l, b, n);
        let digits_r = to_digits(r, b, n);
        let mut dp = vec![vec![vec![vec![-1; 2]; 2]; b+1]; n+1];
        fn dfs(pos: usize, prev: usize, tight_l: usize, tight_r: usize, digits_l: &Vec<usize>, digits_r: &Vec<usize>, b: usize, dp: &mut Vec<Vec<Vec<Vec<i32>>>>) -> i32 {
            if pos == digits_r.len() { return 1; }
            if dp[pos][prev][tight_l][tight_r] != -1 { return dp[pos][prev][tight_l][tight_r]; }
            let mut res = 0;
            let low = if tight_l == 1 { digits_l[pos] } else { 0 };
            let high = if tight_r == 1 { digits_r[pos] } else { b - 1 };
            for d in low..=high {
                if d < prev { continue; }
                res = (res + dfs(pos+1, d, (tight_l == 1 && d == low) as usize, (tight_r == 1 && d == high) as usize, digits_l, digits_r, b, dp)) % MOD;
            }
            dp[pos][prev][tight_l][tight_r] = res;
            res
        }
        fn to_digits(s: &str, base: usize, length: usize) -> Vec<usize> {
            let mut res = vec![0; length];
            let mut num = BigInt::parse_bytes(s.as_bytes(), 10).unwrap();
            for i in (0..length).rev() {
                res[i] = (&num % base).to_usize().unwrap();
                num /= base;
            }
            res
        }
        dfs(0, 0, 1, 1, &digits_l, &digits_r, b, &mut dp)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    countNonDecreasing(l: string, r: string, b: number): number {
        const MOD = 1_000_000_007;
        const n = r.length;
        const digitsL = this.toDigits(l, b, n);
        const digitsR = this.toDigits(r, b, n);
        const dp: number[][][][] = Array.from({length: n+1}, () => Array.from({length: b+1}, () => Array.from({length: 2}, () => Array(2).fill(-1))));
        const dfs = (pos: number, prev: number, tightL: number, tightR: number): number => {
            if (pos === digitsR.length) return 1;
            if (dp[pos][prev][tightL][tightR] !== -1) return dp[pos][prev][tightL][tightR];
            let res = 0;
            const low = tightL === 1 ? digitsL[pos] : 0;
            const high = tightR === 1 ? digitsR[pos] : b - 1;
            for (let d = low; d <= high; d++) {
                if (d < prev) continue;
                res = (res + dfs(pos+1, d, tightL && d === low ? 1 : 0, tightR && d === high ? 1 : 0)) % MOD;
            }
            dp[pos][prev][tightL][tightR] = res;
            return res;
        };
        return dfs(0, 0, 1, 1);
    }
    toDigits(s: string, base: number, length: number): number[] {
        const res: number[] = Array(length).fill(0);
        let num = BigInt(s);
        for (let i = length - 1; i >= 0; i--) {
            res[i] = Number(num % BigInt(base));
            num = num / BigInt(base);
        }
        return res;
    }
}

Complexity

⏰ Time complexity: O(d^2 * log_{b}(N)), where d is the number of digits and N is the upper bound. For each digit, we try up to b choices and memoize by position and previous digit.
🧺 Space complexity: O(d^2 * log_{b}(N)), for the DP memoization table.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Digit DP (Dynamic Programming on Digits)#

Intuition#

Approach#

Code#

Complexity#