Count Numbers with Non-Decreasing Digits
HardUpdated: Aug 2, 2025
Practice on:
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
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
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 <= 1002 <= b <= 10landrconsist only of digits.- The value represented by
lis less than or equal to the value represented byr. landrdo 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], computef(r) - f(l-1).
Code
C++
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;
}
};
Go
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)
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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)
}
}
TypeScript
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.