LeetCode 3519 - Count Numbers with Non-Decreasing Digits

We are given two very large integers l and r as decimal strings and a base b where 2 ≤ b ≤ 10. For every integer x in the inclusive range [l, r], we consider its representation in base b.

leetcodehardmathstringdynamic-programming

LeetCode Problem 3519

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming

Solution

LeetCode 3519 - Count Numbers with Non-Decreasing Digits

Problem Understanding

We are given two very large integers l and r as decimal strings and a base b where 2 ≤ b ≤ 10.

For every integer x in the inclusive range [l, r], we consider its representation in base b. We want to count how many of those representations have digits in non-decreasing order from left to right.

For example, in base 8:

  • 33₈ has digits [3,3], which are non-decreasing.
  • 34₈ has digits [3,4], which are non-decreasing.
  • 32₈ has digits [3,2], which are decreasing, so it does not qualify.

The answer can be extremely large because l and r may contain up to 100 decimal digits. Therefore, brute force enumeration is impossible. We must return the answer modulo 10^9 + 7.

The key challenge is that the input numbers are provided in decimal, while the digit ordering constraint must be checked in base b.

The constraints immediately suggest that:

  • We cannot convert the entire interval into integers.
  • We cannot iterate through the range.
  • We need a counting approach.
  • Since the condition depends on the digit structure of a number, this is a classic digit-DP problem.

Some important edge cases include:

  • Very large numbers with up to 100 decimal digits.
  • Base 2, where valid representations are extremely restricted.
  • Ranges containing a single number.
  • Numbers whose base-b representation contains many leading positions during DP construction.
  • The lower bound being 1, requiring careful handling of count(≤ r) - count(< l).

Approaches

Brute Force

A straightforward solution would iterate through every integer in [l, r].

For each number:

  1. Convert it to base b.
  2. Check whether every digit is at least as large as the previous digit.
  3. Increment the answer if the condition holds.

This approach is obviously correct because it directly evaluates the definition.

However, it is completely infeasible. The interval length may be astronomically large because the endpoints themselves may contain up to 100 decimal digits.

Even for intervals of size 10^12, brute force would already be impossible.

Key Insight

Instead of counting numbers individually, we count all valid numbers up to a bound N.

Define:

$$F(N) = \text{count of integers } x \le N \text{ whose base-}b\text{ digits are non-decreasing}$$

Then the required answer becomes:

$$F(r) - F(l-1)$$

The property depends only on the digits of the base-b representation.

Therefore:

  1. Convert the decimal string bound into base b.
  2. Perform digit DP over the base-b digits.
  3. Track:
  • Current position.
  • Previous chosen digit.
  • Whether a non-leading digit has already been placed.
  • Whether we are still tight to the upper bound.

Whenever we place a new digit after the number has started, it must satisfy:

$$digit \ge previousDigit$$

This guarantees the resulting representation is non-decreasing.

Because the number of base-b digits for a 100-digit decimal number is only about 333 in base 2, the state space remains very small.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((r-l+1) · log_b(r)) O(log_b(r)) Enumerates every number
Optimal O(L · b²) O(L · b) Digit DP over base-b representation

Here L denotes the number of digits of the bound in base b.

Algorithm Walkthrough

  1. Create a function that converts a decimal string into a base-b digit array. Since the number may have 100 decimal digits, ordinary integer conversion cannot be used in every language. Instead, repeatedly perform string division by b.
  2. Create a function minusOne(s) that subtracts one from a decimal string. This is needed to compute F(l-1).
  3. Define countUpTo(decimalString).
  4. Convert the decimal string into its base-b digit sequence.
  5. Use digit DP with state:
  • pos, current digit position.
  • prev, previous chosen digit.
  • started, whether a non-leading digit has been placed.
  • tight, whether all previous digits match the bound.
  1. If we reach the end of the digit array:
  • Return 1 if a number has started.
  • Return 0 otherwise.

This excludes zero, since the problem range begins from positive integers. 7. Let limit be:

  • The bound digit if tight = true.
  • b-1 otherwise.
  1. Try every digit from 0 to limit.
  2. If the number has not started yet:
  • Choosing 0 keeps us in the leading-zero state.
  • Choosing a nonzero digit starts the number.
  1. Once the number has started:
  • Every newly chosen digit must satisfy digit >= prev.
  • Otherwise that transition is invalid.
  1. Recurse to the next position and accumulate results modulo 10^9+7.
  2. The final answer is:

$$(F(r)-F(l-1)+MOD)\bmod MOD$$

Why it works

The DP constructs every number less than or equal to the bound exactly once. The tight flag guarantees we never exceed the bound. The started flag correctly handles leading zeros. The prev value enforces the non-decreasing constraint at every step. Since every valid number corresponds to exactly one DP path and every DP path corresponds to a unique valid number, the count is exact.

Problem Understanding

This problem asks us to count the numbers within a given inclusive range [l, r] whose digits, when expressed in a given base b, are non-decreasing. Non-decreasing digits mean that as you read the number from left to right (most significant to least significant digit), each digit is greater than or equal to the one before it. For example, in base 10, the number 233 is non-decreasing, while 232 is not.

The inputs are strings l and r representing the lower and upper bounds of the range. They are strings rather than integers to handle very large numbers that might exceed standard integer types. The base b is an integer between 2 and 10, so the digits of numbers will range from 0 to b-1.

The output is a single integer, the count of non-decreasing numbers in the range [l, r], modulo $10^9 + 7$.

Constraints tell us that l and r can be up to 100 digits long, which immediately rules out iterating through every number in the range. Also, all inputs are valid positive integers without leading zeros, and l <= r.

Edge cases to consider include very small ranges (e.g., l = r), numbers with single digits, and situations where the range crosses powers of the base, since digit patterns reset at powers of the base.

Approaches

Brute Force Approach

A naive solution would iterate from l to r, convert each number to base b, and check if the digits are non-decreasing. While this approach is straightforward and guaranteed to produce the correct answer, it is infeasible for large inputs. With l and r potentially having 100 digits, the number of integers to check can exceed $10^{100}$, which is astronomically large.

Optimal Approach

The key insight is that this problem can be solved using digit dynamic programming (digit DP). Instead of iterating over each number, we reason about each position of the number in base b and count how many valid numbers exist that satisfy the non-decreasing property.

We define a recursive function dfs(pos, tight, prev_digit) that counts numbers from the current position pos:

  • pos represents the current digit position in the number we are building.
  • tight indicates whether the current prefix matches the original number prefix (l or r), which ensures we don’t exceed the bound.
  • prev_digit is the previous digit chosen, ensuring non-decreasing order.

At each step, we iterate over valid digits for the current position (prev_digit to b-1 if non-decreasing). Memoization is used to store results of subproblems, avoiding repeated calculations.

To count numbers in the inclusive range [l, r], we compute the count of valid numbers up to r and subtract the count up to l-1.

Approach Time Complexity Space Complexity Notes
Brute Force O(r-l) O(1) Iterate all numbers, convert to base b, check digits
Optimal O(L * B * B) O(L * B) Digit DP on number length L and base B with memoization

Algorithm Walkthrough

  1. Convert the target number (l or r) to a list of digits in base b. This allows us to reason about each digit position independently.
  2. Define a recursive function dfs(pos, tight, prev_digit) to count numbers with non-decreasing digits starting at position pos. tight ensures we do not exceed the number’s digits, and prev_digit guarantees non-decreasing order.
  3. For the current position, determine the valid range of digits. If tight is true, the maximum digit is limited by the corresponding digit in the number; otherwise, it is b-1.
  4. Iterate over all valid digits, recursively computing counts for the next position, updating tight to reflect whether the chosen digit equals the limit.
  5. Base case: when pos reaches the length of the number, return 1 to indicate a valid number has been formed.
  6. Memoize results by storing (pos, tight, prev_digit) to avoid recomputation.
  7. To compute the final count for [l, r], calculate count(r) - count(l-1) modulo $10^9 + 7$.
  8. Implement a helper function to decrement l by 1 in base b to handle the lower bound.

Why it works: The digit DP ensures that all numbers generated follow the non-decreasing property while respecting bounds. Memoization ensures each subproblem is solved once, guaranteeing efficiency.

Python Solution

from functools import lru_cache
from typing import List

class Solution:
    def countNumbers(self, l: str, r: str, b: int) -> int:
        MOD = 1_000_000_007

        def minus_one(s: str) -> str:
            arr = list(s)
            i = len(arr) - 1

            while i >= 0 and arr[i] == '0':
                arr[i] = '9'
                i -= 1

            if i >= 0:
                arr[i] = str(int(arr[i]) - 1)

            result = ''.join(arr).lstrip('0')
            return result if result else "0"

        def decimal_to_base(num: str) -> List[int]:
            if num == "0":
                return [0]

            digits = []
            current = num

            while current != "0":
                quotient = []
                carry = 0

                for ch in current:
                    carry = carry * 10 + int(ch)
                    quotient_digit = carry // b
                    carry %= b

                    if quotient or quotient_digit:
                        quotient.append(str(quotient_digit))

                digits.append(carry)
                current = ''.join(quotient) if quotient else "0"

            return digits[::-1]

        def count_up_to(num: str) -> int:
            if num == "0":
                return 0

            digits = decimal_to_base(num)
            n = len(digits)

            @lru_cache(None)
            def dp(pos: int, prev: int, started: int, tight: int) -> int:
                if pos == n:
                    return 1 if started else 0

                limit = digits[pos] if tight else b - 1
                ans = 0

                for digit in range(limit + 1):
                    next_tight = tight and (digit == limit)

                    if not started:
                        if digit == 0:
                            ans += dp(
                                pos + 1,
                                0,
                                0,
                                next_tight
                            )
                        else:
                            ans += dp(
                                pos + 1,
                                digit,
                                1,
                                next_tight
                            )
                    else:
                        if digit >= prev:
                            ans += dp(
                                pos + 1,
                                digit,
                                1,
                                next_tight
                            )

                return ans % MOD

            return dp(0, 0, 0, 1)

        left_minus_one = minus_one(l)
        answer = (count_up_to(r) - count_up_to(left_minus_one)) % MOD
        return answer

Implementation Explanation

The solution is organized around the standard digit-DP pattern.

The minus_one helper computes l-1 directly on the decimal string without converting it into a built-in integer.

The decimal_to_base helper repeatedly divides the decimal string by b. This produces the base-b representation even for numbers containing hundreds of digits.

The core work happens in count_up_to.

After obtaining the base-b digit array, the memoized DP explores all valid digit assignments.

The started flag distinguishes leading zeros from actual digits. While started is false, zeros do not participate in the monotonicity constraint. Once a nonzero digit is placed, every subsequent digit must satisfy digit >= prev.

Memoization ensures each state is solved only once.

Finally, inclusion-exclusion computes the answer for the requested interval. class Solution: MOD = 10**9 + 7

def countNumbers(self, l: str, r: str, b: int) -> int:
    def str_to_base_digits(s: str) -> list[int]:
        num = int(s)
        digits = []
        if num == 0:
            return [0]
        while num > 0:
            digits.append(num % b)
            num //= b
        return digits[::-1]

    from functools import lru_cache

    def count_up_to(n: list[int]) -> int:
        @lru_cache(None)
        def dfs(pos: int, tight: bool, prev: int) -> int:
            if pos == len(n):
                return 1
            limit = n[pos] if tight else b - 1
            total = 0
            for d in range(prev, limit + 1):
                total += dfs(pos + 1, tight and d == limit, d)
                total %= self.MOD
            return total

        return dfs(0, True, 0)

    def decrement_str(s: str) -> str:
        num = int(s)
        return str(num - 1) if num > 0 else "0"

    digits_r = str_to_base_digits(r)
    digits_l_minus_1 = str_to_base_digits(decrement_str(l))
    result = (count_up_to(digits_r) - count_up_to(digits_l_minus_1)) % self.MOD
    return result


**Implementation Explanation**:

We first convert numbers to base `b` digits for easy DP handling. The `dfs` function recursively counts valid numbers with memoization. The decrement function adjusts the lower bound so the inclusive range can be computed as `count(r) - count(l-1)`. Modulo operations ensure large counts do not overflow.

## Go Solution

```go
package main

const MOD int = 1000000007

func countNumbers(l string, r string, b int) int {
	minusOne := func(s string) string {
		arr := []byte(s)
		i := len(arr) - 1

		for i >= 0 && arr[i] == '0' {
			arr[i] = '9'
			i--
		}

		if i >= 0 {
			arr[i]--
		}

		start := 0
		for start < len(arr) && arr[start] == '0' {
			start++
		}

		if start == len(arr) {
			return "0"
		}

		return string(arr[start:])
	}

	var decimalToBase func(string) []int

	decimalToBase = func(num string) []int {
		if num == "0" {
			return []int{0}
		}

		var digits []int
		current := num

		for current != "0" {
			quotient := make([]byte, 0)
			carry := 0

			for i := 0; i < len(current); i++ {
				carry = carry*10 + int(current[i]-'0')

				q := carry / b
				carry %= b

				if len(quotient) > 0 || q > 0 {
					quotient = append(quotient, byte(q)+'0')
				}
			}

			digits = append(digits, carry)

			if len(quotient) == 0 {
				current = "0"
			} else {
				current = string(quotient)
			}
		}

		for i, j := 0, len(digits)-1; i < j; i, j = i+1, j-1 {
			digits[i], digits[j] = digits[j], digits[i]
		}

		return digits
	}

	type State struct {
		pos     int
		prev    int
		started int
		tight   int
	}

	var countUpTo func(string) int

	countUpTo = func(num string) int {
		if num == "0" {
			return 0
		}

		digits := decimalToBase(num)
		n := len(digits)

		memo := make(map[State]int)

		var dp func(int, int, int, int) int

		dp = func(pos int, prev int, started int, tight int) int {
			if pos == n {
				if started == 1 {
					return 1
				}
				return 0
			}

			state := State{pos, prev, started, tight}

			if val, ok := memo[state]; ok {
				return val
			}

			limit := b - 1
			if tight == 1 {
				limit = digits[pos]
			}

			ans := 0

			for digit := 0; digit <= limit; digit++ {
				nextTight := 0
				if tight == 1 && digit == limit {
					nextTight = 1
				}

				if started == 0 {
					if digit == 0 {
						ans += dp(pos+1, 0, 0, nextTight)
					} else {
						ans += dp(pos+1, digit, 1, nextTight)
					}
				} else {
					if digit >= prev {
						ans += dp(pos+1, digit, 1, nextTight)
					}
				}

				ans %= MOD
			}

			memo[state] = ans
			return ans
		}

		return dp(0, 0, 0, 1)
	}

	leftMinusOne := minusOne(l)

	ans := countUpTo(r) - countUpTo(leftMinusOne)
	ans %= MOD

	if ans < 0 {
		ans += MOD
	}

	return ans
}

Go-Specific Notes

The Go version mirrors the Python implementation almost exactly.

Because Go does not provide built-in memoization decorators, a map[State]int is used. The DP state is represented by a small struct containing the four state variables.

All arithmetic is performed modulo 1e9+7 to prevent growth of intermediate values.

Worked Examples

Example 1

Input:

l = "23"
r = "28"
b = 8

The base-8 representations are:

Decimal Base 8 Valid
23 27 Yes
24 30 No
25 31 No
26 32 No
27 33 Yes
28 34 Yes

Result:

3

From the DP perspective:

Position Previous Digit Allowed Digits
First digit none 1..3
Second digit after 2 2..7
Second digit after 3 3..4 (bounded by r)

The valid paths correspond exactly to:

27
33
34

Example 2

Input:

l = "2"
r = "7"
b = 2

Representations:

Decimal Binary Valid
2 10 No
3 11 Yes
4 100 No
5 101 No
6 110 No
7 111 Yes

Result:

2

The DP only accepts sequences where every digit is at least the previous digit. In binary, that means once a digit becomes 1, all following digits must also be 1.

Thus only:

11
111

are counted.

Complexity Analysis

Measure Complexity Explanation
Time O(L · b²) Each DP state explores up to b transitions
Space O(L · b) Memoization table stores all reachable states

Here L is the number of digits of the bound in base b.

Since b ≤ 10, the base factor is tiny. Even for a 100-digit decimal number, L is only about 333 in base 2, making the solution easily fast enough.

Test Cases

sol = Solution()

assert sol.countNumbers("23", "28", 8) == 3  # example 1
assert sol.countNumbers("2", "7", 2) == 2    # example 2

assert sol.countNumbers("1", "1", 2) == 1    # single valid number
assert sol.countNumbers("2", "2", 2) == 0    # binary 10 is invalid

assert sol.countNumbers("3", "3", 2) == 1    # binary 11 is valid

assert sol.countNumbers("7", "7", 2) == 1    # binary 111

assert sol.countNumbers("8", "8", 8) == 0    # 10 in base 8

assert sol.countNumbers("9", "9", 8) == 1    # 11 in base 8

assert sol.countNumbers("1", "9", 10) == 9   # all single-digit numbers

assert sol.countNumbers("10", "12", 10) == 2 # 11 and 12

assert sol.countNumbers("98", "102", 10) == 1 # only 99 qualifies

assert sol.countNumbers("1000", "1000", 10) == 0 # decreasing digits

assert sol.countNumbers("1111", "1111", 10) == 1 # equal digits

assert sol.countNumbers(
    "1",
    "999999999999999999999999999999",
    10
) >= 0  # large stress test

Test Summary

Test Why
(23,28,8) Official example 1
(2,7,2) Official example 2
(1,1,2) Smallest valid range
(2,2,2) Single invalid number
(3,3,2) Single valid number
(7,7,2) All ones in binary
(8,8,8) Representation 10
(9,9,8) Representation 11
(1,9,10) All one-digit values
(10,12,10) Small decimal interval
(98,102,10) Crossing digit length boundary
(1000,1000,10) Internal decrease
(1111,1111,10) Equal digits throughout
Huge upper bound Stress test for large input

Edge Cases

Range Contains a Single Number

When l == r, the answer should be either 0 or 1. Some interval counting solutions accidentally overcount due to incorrect inclusion-exclusion logic. Computing F(r) - F(l-1) avoids this problem and correctly handles singleton intervals.

Base 2

Binary representations place the strongest restriction on non-decreasing digits. Once a digit becomes 1, all later digits must also be 1. This creates many invalid numbers. The DP naturally enforces the ordering condition through the prev state and does not require any special-case logic.

Numbers with Different Representation Lengths

The interval may span numbers whose base-b representations have different lengths. A naive fixed-length approach can accidentally impose constraints on leading zeros. The started flag prevents leading zeros from participating in the non-decreasing comparison, allowing all representation lengths to be handled correctly within one DP.

Very Large Decimal Inputs

The inputs may contain up to 100 decimal digits, far exceeding standard integer types. Converting directly to 64-bit integers would overflow. The implementation performs repeated string division to obtain the base-b digits, making it safe for arbitrarily large values within the problem constraints.

Lower Bound Equal to One

When l = "1", we must evaluate F(0). The implementation explicitly returns 0 for countUpTo("0"), ensuring inclusion-exclusion remains correct and avoiding negative-number handling entirely. import "strconv"

const MOD = 1_000_000_007

func countNumbers(l string, r string, b int) int { var strToBaseDigits = func(s string) []int { num, _ := strconv.Atoi(s) if num == 0 { return []int{0} } digits := []int{} for num > 0 { digits = append([]int{num % b}, digits...) num /= b } return digits }

var decrementStr = func(s string) string {
    num, _ := strconv.Atoi(s)
    if num == 0 {
        return "0"
    }
    return strconv.Itoa(num - 1)
}

memo := map[[3]int]int{}
var dfs func([]int, int, bool, int) int
dfs = func(n []int, pos int, tight bool, prev int) int {
    key := [3]int{pos, boolToInt(tight), prev}
    if val, ok := memo[key]; ok {
        return val
    }
    if pos == len(n) {
        return 1
    }
    limit := b - 1
    if tight {
        limit = n[pos]
    }
    total := 0
    for d := prev; d <= limit; d++ {
        total = (total + dfs(n, pos+1, tight && d == limit, d)) % MOD
    }
    memo[key] = total
    return total
}

var boolToInt = func(b bool) int {
    if b {
        return 1
    }
    return 0
}

digitsR := strToBaseDigits(r)
digitsLMinus1 := strToBaseDigits(decrementStr(l))
result := (dfs(digitsR, 0, true, 0) - dfs(digitsLMinus1, 0, true, 0) + MOD) % MOD
return result

}


**Go-specific Notes**:

We use a `map[[3]int]int` for memoization instead of `lru_cache`. Conversion to base `b` is done using slices. Boolean flags are converted to integers for map keys. All arithmetic is modulo `MOD` to prevent overflow.

## Worked Examples

**Example 1: l = "23", r = "28", b = 8**

1. Convert to base 8 digits:

- 23 → 27 in base 8 → digits [2, 7]
- 28 → 34 in base 8 → digits [3, 4]
2. Use digit DP to count numbers ≤ 34 with non-decreasing digits:

- 27 → digits [2, 7] → non-decreasing
- 30 → digits [3, 0] → decreasing → invalid
- 31 → digits [3, 1] → decreasing → invalid
-