Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 109 + 7.
Example 1:
Input: l = "23", r = "28", b = 8
Output: 3
Explanation:
Example 2:
Input: l = "2", r = "7", b = 2
Output: 2
Explanation:
Constraints:
1 <= l.length <= r.length <= 1002 <= b <= 10l and r consist only of digits.l is less than or equal to the value represented by r.l and r do not contain leading zeros.Problem summary: 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 109 + 7.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Dynamic Programming
"23" "28" 8
"2" "7" 2
count-of-integers)number-of-beautiful-integers-in-the-range)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3519: Count Numbers with Non-Decreasing Digits
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3519: Count Numbers with Non-Decreasing Digits
// package main
//
// import (
// "fmt"
// "math/big"
// "strings"
// )
//
// // https://space.bilibili.com/206214
// const mod = 1_000_000_007
// const maxN = 333 // 进制转换后的最大长度
// const maxB = 10
//
// var comb [maxN + maxB][maxB]int
//
// func init() {
// // 预处理组合数
// for i := 0; i < len(comb); i++ {
// comb[i][0] = 1
// for j := 1; j < min(i+1, maxB); j++ {
// // 注意本题组合数较小，无需取模
// comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
// }
// }
// }
//
// func trans(s string, b int, inc bool) string {
// x := &big.Int{}
// fmt.Fscan(strings.NewReader(s), x)
// if inc {
// x.Add(x, big.NewInt(1))
// }
// return x.Text(b) // 转成 b 进制
// }
//
// func calc(s string, b int, inc bool) (res int) {
// s = trans(s, b, inc)
// // 计算小于 s 的合法数字个数
// // 为什么是小于？注意下面的代码，我们没有统计每个数位都填 s[i] 的情况
// pre := 0
// for i, d := range s {
// hi := int(d - '0')
// if hi < pre {
// break
// }
// m := len(s) - 1 - i
// res += comb[m+b-pre][b-1-pre] - comb[m+b-hi][b-1-hi]
// pre = hi
// }
// return
// }
//
// func countNumbers(l, r string, b int) int {
// // 小于 r+1 的合法数字个数 - 小于 l 的合法数字个数
// return (calc(r, b, true) - calc(l, b, false)) % mod
// }
// Accepted solution for LeetCode #3519: Count Numbers with Non-Decreasing Digits
package main
import (
"fmt"
"math/big"
"strings"
)
// https://space.bilibili.com/206214
const mod = 1_000_000_007
const maxN = 333 // 进制转换后的最大长度
const maxB = 10
var comb [maxN + maxB][maxB]int
func init() {
// 预处理组合数
for i := 0; i < len(comb); i++ {
comb[i][0] = 1
for j := 1; j < min(i+1, maxB); j++ {
// 注意本题组合数较小，无需取模
comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
}
}
}
func trans(s string, b int, inc bool) string {
x := &big.Int{}
fmt.Fscan(strings.NewReader(s), x)
if inc {
x.Add(x, big.NewInt(1))
}
return x.Text(b) // 转成 b 进制
}
func calc(s string, b int, inc bool) (res int) {
s = trans(s, b, inc)
// 计算小于 s 的合法数字个数
// 为什么是小于？注意下面的代码，我们没有统计每个数位都填 s[i] 的情况
pre := 0
for i, d := range s {
hi := int(d - '0')
if hi < pre {
break
}
m := len(s) - 1 - i
res += comb[m+b-pre][b-1-pre] - comb[m+b-hi][b-1-hi]
pre = hi
}
return
}
func countNumbers(l, r string, b int) int {
// 小于 r+1 的合法数字个数 - 小于 l 的合法数字个数
return (calc(r, b, true) - calc(l, b, false)) % mod
}
# Accepted solution for LeetCode #3519: Count Numbers with Non-Decreasing Digits
#
# @lc app=leetcode id=3519 lang=python3
#
# [3519] Count Numbers with Non-Decreasing Digits
#
# @lc code=start
import sys
# Increase recursion depth for deep DP trees if necessary
sys.setrecursionlimit(2000)
class Solution:
def countNumbers(self, l: str, r: str, b: int) -> int:
MOD = 10**9 + 7
def get_base_b_digits(n_str, b):
# Convert base-10 string to integer
n = int(n_str)
if n == 0:
return [0]
digits = []
while n > 0:
digits.append(n % b)
n //= b
return digits[::-1]
def solve(digits):
n = len(digits)
memo = {}
def dp(index, prev_digit, is_less, is_started):
state = (index, prev_digit, is_less, is_started)
if state in memo:
return memo[state]
if index == n:
return 1 # Found one valid number
res = 0
limit = digits[index] if not is_less else b - 1
# Determine the range of digits we can place
# If not started, we can place 0 (which keeps it not started)
# or 1..limit (which starts it).
# If started, we must place digit >= prev_digit.
start = 0
end = limit
for d in range(start, end + 1):
if not is_started:
if d == 0:
# Still not started, effectively skipping this position (leading zero)
# However, we must be careful. The DP structure generally builds a number of length `n`.
# If we place a 0 here and remain !is_started, we are effectively building a number with fewer digits.
# But wait, does this specific DP structure count 0?
# If we reach index == n and !is_started, we formed the number 0.
# The range is usually inclusive. If the input number is 5, we count 0, 1, 2, 3, 4, 5.
# Let's assume we count 0 as valid if it's non-decreasing (0 is trivially non-decreasing).
# But if the actual number we are counting <= N is 0, is_started will be false until end.
# Special case: If we are at the last position and haven't started, placing 0 makes the number 0.
# Usually "leading zeros" logic is used to count numbers with fewer digits.
# If we place 0 and don't start, we move to next index.
new_is_less = is_less or (d < limit)
res = (res + dp(index + 1, 0, new_is_less, False)) % MOD
else:
# Start the number. Since it's the first digit, constraint is just d > 0.
new_is_less = is_less or (d < limit)
res = (res + dp(index + 1, d, new_is_less, True)) % MOD
else:
# Already started, must be >= prev_digit
if d >= prev_digit:
new_is_less = is_less or (d < limit)
res = (res + dp(index + 1, d, new_is_less, True)) % MOD
memo[state] = res
return res
return dp(0, 0, False, False)
# Convert l and r to base b digits
# We need count(r) - count(l-1)
# Helper to handle the subtraction logic for l-1
def count_le(n_str):
digits = get_base_b_digits(n_str, b)
# The DP counts numbers in [0, n_str].
# 0 is always non-decreasing (single digit).
return solve(digits)
ans_r = count_le(r)
# Calculate l-1 string
l_int = int(l)
ans_l_minus_1 = 0
if l_int > 0:
ans_l_minus_1 = count_le(str(l_int - 1))
return (ans_r - ans_l_minus_1 + MOD) % MOD
# @lc code=end
// Accepted solution for LeetCode #3519: Count Numbers with Non-Decreasing Digits
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3519: Count Numbers with Non-Decreasing Digits
// package main
//
// import (
// "fmt"
// "math/big"
// "strings"
// )
//
// // https://space.bilibili.com/206214
// const mod = 1_000_000_007
// const maxN = 333 // 进制转换后的最大长度
// const maxB = 10
//
// var comb [maxN + maxB][maxB]int
//
// func init() {
// // 预处理组合数
// for i := 0; i < len(comb); i++ {
// comb[i][0] = 1
// for j := 1; j < min(i+1, maxB); j++ {
// // 注意本题组合数较小，无需取模
// comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
// }
// }
// }
//
// func trans(s string, b int, inc bool) string {
// x := &big.Int{}
// fmt.Fscan(strings.NewReader(s), x)
// if inc {
// x.Add(x, big.NewInt(1))
// }
// return x.Text(b) // 转成 b 进制
// }
//
// func calc(s string, b int, inc bool) (res int) {
// s = trans(s, b, inc)
// // 计算小于 s 的合法数字个数
// // 为什么是小于？注意下面的代码，我们没有统计每个数位都填 s[i] 的情况
// pre := 0
// for i, d := range s {
// hi := int(d - '0')
// if hi < pre {
// break
// }
// m := len(s) - 1 - i
// res += comb[m+b-pre][b-1-pre] - comb[m+b-hi][b-1-hi]
// pre = hi
// }
// return
// }
//
// func countNumbers(l, r string, b int) int {
// // 小于 r+1 的合法数字个数 - 小于 l 的合法数字个数
// return (calc(r, b, true) - calc(l, b, false)) % mod
// }
// Accepted solution for LeetCode #3519: Count Numbers with Non-Decreasing Digits
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3519: Count Numbers with Non-Decreasing Digits
// package main
//
// import (
// "fmt"
// "math/big"
// "strings"
// )
//
// // https://space.bilibili.com/206214
// const mod = 1_000_000_007
// const maxN = 333 // 进制转换后的最大长度
// const maxB = 10
//
// var comb [maxN + maxB][maxB]int
//
// func init() {
// // 预处理组合数
// for i := 0; i < len(comb); i++ {
// comb[i][0] = 1
// for j := 1; j < min(i+1, maxB); j++ {
// // 注意本题组合数较小，无需取模
// comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
// }
// }
// }
//
// func trans(s string, b int, inc bool) string {
// x := &big.Int{}
// fmt.Fscan(strings.NewReader(s), x)
// if inc {
// x.Add(x, big.NewInt(1))
// }
// return x.Text(b) // 转成 b 进制
// }
//
// func calc(s string, b int, inc bool) (res int) {
// s = trans(s, b, inc)
// // 计算小于 s 的合法数字个数
// // 为什么是小于？注意下面的代码，我们没有统计每个数位都填 s[i] 的情况
// pre := 0
// for i, d := range s {
// hi := int(d - '0')
// if hi < pre {
// break
// }
// m := len(s) - 1 - i
// res += comb[m+b-pre][b-1-pre] - comb[m+b-hi][b-1-hi]
// pre = hi
// }
// return
// }
//
// func countNumbers(l, r string, b int) int {
// // 小于 r+1 的合法数字个数 - 小于 l 的合法数字个数
// return (calc(r, b, true) - calc(l, b, false)) % mod
// }
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.