Difficulty: 🔴 Hard
Topics: Math, Divide and Conquer, Combinatorics, Number Theory

Solution

LeetCode 3855 - Sum of K-Digit Numbers in a Range

Problem Understanding

We are given three integers l, r, and k.

For every digit position, we may independently choose any digit from the inclusive range [l, r]. We then form all possible numbers consisting of exactly k digits.

A key detail is that if 0 belongs to the allowed digit range, leading zeros are permitted. This means we are not generating ordinary decimal integers with a fixed number of digits. Instead, we are generating all length-k digit strings and interpreting each string as a decimal number.

For example, if l = 0, r = 1, and k = 3, the valid digit strings are:

These are interpreted as decimal values:

The task is to compute the sum of all such numbers and return the answer modulo 10^9 + 7.

The constraints are extremely important:

0 <= l <= r <= 9
1 <= k <= 10^9

The digit range is tiny, but k can be as large as one billion. This immediately tells us that any algorithm that iterates over digit positions one by one will be too slow. We need a mathematical formula combined with fast exponentiation.

Some important edge cases include:

Only one digit is allowed (l = r).
The digit range contains zero, meaning leading zeros contribute valid numbers.
k = 1.
Very large k, up to 10^9.
The range may contain all digits from 0 through 9.

These cases suggest that the solution must rely entirely on combinatorial counting rather than explicit generation.

Approaches

Brute Force

The most direct approach is to generate every possible length-k digit string.

If there are

$$m = r - l + 1$$

available digits, then there are

$$m^k$$

different numbers.

For each generated number, we could convert it into its decimal value and add it to the running sum.

This approach is correct because it explicitly enumerates every valid number exactly once and accumulates their values.

Unfortunately, it is completely infeasible. Even for moderate values such as m = 10 and k = 20, the number of possibilities is already 10^20.

Key Insight

Instead of summing numbers individually, we can compute the contribution of each digit position independently.

Every number can be written as:

$$d_0 \cdot 10^{k-1} + d_1 \cdot 10^{k-2} + \cdots + d_{k-1}$$

Because digit choices are independent, each position behaves identically.

For a fixed position:

The digit can be any value from [l, r].
Every digit appears the same number of times.
The remaining k-1 positions can be chosen arbitrarily.

This allows us to count the total contribution of one position mathematically and multiply by the sum of positional weights.

The only remaining challenge is efficiently computing:

$$1 + 10 + 10^2 + \cdots + 10^{k-1}$$

for k up to 10^9, which can be done using a geometric-series formula under modular arithmetic.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((r-l+1)^k \cdot k)	O(k)	Generates every possible number
Optimal	O(log k)	O(1)	Uses combinatorial counting and geometric series

Algorithm Walkthrough

Step 1: Count the available digits

Let

$$m = r - l + 1$$

This is the number of possible choices for every digit position.

Step 2: Compute the sum of allowed digits

Let

$$S = l + (l+1) + \cdots + r$$

Using the arithmetic-series formula:

$$S = \frac{(l+r)m}{2}$$

This represents the total value contributed when considering all possible digit choices for a single position.

Step 3: Count how many times each position pattern occurs

Fix any position.

Once the digit for that position is chosen, the remaining k-1 positions can be assigned freely.

Therefore there are

$$m^{k-1}$$

completions for every chosen digit.

Thus the total digit contribution for one position is

$$S \cdot m^{k-1}$$

Step 4: Compute positional weights

The decimal weight of the positions is

$$10^{k-1} + 10^{k-2} + \cdots + 10^0$$

which is equivalent to

$$1 + 10 + 10^2 + \cdots + 10^{k-1}$$

We need this value modulo 10^9+7.

Step 5: Compute the geometric series efficiently

The geometric sum is

$$G = 1 + 10 + 10^2 + \cdots + 10^{k-1} = \frac{10^k - 1}{9}$$

Under modular arithmetic:

$$G = (10^k - 1) \cdot 9^{-1} \pmod M$$

where

$$M = 10^9 + 7$$

and 9^{-1} is the modular inverse of 9.

Step 6: Combine everything

Each position contributes:

$$S \cdot m^{k-1}$$

and the positional weights sum to G.

Therefore the final answer is

$$S \cdot m^{k-1} \cdot G \pmod M$$

Why it works

The key invariant is that every position is statistically identical. For any fixed position, every allowed digit appears exactly m^(k-1) times because all remaining positions are chosen independently. Therefore the total contribution of a position equals the sum of allowed digits multiplied by the number of completions. Since decimal numbers are linear combinations of positional contributions, summing the contributions of all positions produces exactly the sum of all generated numbers.

Python Solution

class Solution:
    def sumOfNumbers(self, l: int, r: int, k: int) -> int:
        MOD = 1_000_000_007

        digit_count = r - l + 1
        digit_sum = (l + r) * digit_count // 2

        ways = pow(digit_count, k - 1, MOD)

        inv9 = pow(9, MOD - 2, MOD)
        geometric_sum = (pow(10, k, MOD) - 1) % MOD
        geometric_sum = geometric_sum * inv9 % MOD

        return digit_sum % MOD * ways % MOD * geometric_sum % MOD

The implementation follows the mathematical derivation directly.

First, it computes the number of available digits and the sum of those digits. Next, it calculates m^(k-1) using modular exponentiation. This gives the number of times each digit value appears in a fixed position.

The geometric series

$$1 + 10 + \cdots + 10^{k-1}$$

is then computed using the closed-form formula and a modular inverse of 9.

Finally, the three factors are multiplied together modulo 10^9 + 7.

Because Python's built-in pow(base, exp, mod) performs fast exponentiation, the solution runs in logarithmic time.

Go Solution

func sumOfNumbers(l int, r int, k int) int {
	const MOD int64 = 1_000_000_007

	modPow := func(base, exp int64) int64 {
		result := int64(1)
		base %= MOD

		for exp > 0 {
			if exp&1 == 1 {
				result = result * base % MOD
			}
			base = base * base % MOD
			exp >>= 1
		}

		return result
	}

	digitCount := int64(r - l + 1)
	digitSum := int64((l + r) * (r - l + 1) / 2)

	ways := modPow(digitCount, int64(k-1))

	inv9 := modPow(9, MOD-2)

	geometricSum := (modPow(10, int64(k)) - 1 + MOD) % MOD
	geometricSum = geometricSum * inv9 % MOD

	ans := digitSum % MOD
	ans = ans * ways % MOD
	ans = ans * geometricSum % MOD

	return int(ans)
}

The Go solution uses iterative binary exponentiation because Go does not provide a built-in modular exponentiation function equivalent to Python's three-argument pow.

All arithmetic is performed with int64 values to avoid overflow during intermediate multiplications. The final result is converted back to int before returning.

Worked Examples

Example 1

Input:

l = 1
r = 2
k = 2

Compute basic values:

Variable	Value
m	2
S	1 + 2 = 3
m^(k-1)	2
G	1 + 10 = 11

Final answer:

Expression	Value
S × m^(k-1)	3 × 2 = 6
6 × G	6 × 11 = 66

Result:

Example 2

Input:

l = 0
r = 1
k = 3

Compute values:

Variable	Value
m	2
S	1
m^(k-1)	4
G	1 + 10 + 100 = 111

Final answer:

Expression	Value
S × m^(k-1)	1 × 4 = 4
4 × G	4 × 111 = 444

Result:

Example 3

Input:

l = 5
r = 5
k = 10

Compute values:

Variable	Value
m	1
S	5
m^(k-1)	1
G	1111111111

Final formula:

Expression	Value
5 × 1 × 1111111111	5555555555

Modulo:

5555555555 mod (1e9+7) = 555555520

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log k)	Two modular exponentiations dominate the running time
Space	O(1)	Only a constant number of variables are used

The solution never iterates over digit positions or generated numbers. All heavy computation is performed using binary exponentiation, which requires only logarithmically many multiplications. Since no auxiliary data structures grow with the input size, the space usage remains constant.

Test Cases

sol = Solution()

assert sol.sumOfNumbers(1, 2, 2) == 66          # Example 1
assert sol.sumOfNumbers(0, 1, 3) == 444         # Example 2
assert sol.sumOfNumbers(5, 5, 10) == 555555520  # Example 3

assert sol.sumOfNumbers(0, 0, 1) == 0           # Single zero digit
assert sol.sumOfNumbers(9, 9, 1) == 9           # Single nonzero digit
assert sol.sumOfNumbers(0, 9, 1) == 45          # Sum of all digits

assert sol.sumOfNumbers(1, 1, 5) == 11111       # Only one possible number
assert sol.sumOfNumbers(0, 0, 1000000000) == 0  # Huge k, all zeros

assert sol.sumOfNumbers(0, 9, 2) == 4950        # All two-digit strings
assert sol.sumOfNumbers(3, 7, 1) == 25          # Simple range

# Stress case, verifies logarithmic exponentiation
sol.sumOfNumbers(0, 9, 1000000000)

Test Summary

Test	Why
`(1,2,2)`	First example
`(0,1,3)`	Leading zeros allowed
`(5,5,10)`	Single valid number
`(0,0,1)`	Smallest possible value
`(9,9,1)`	Largest single digit
`(0,9,1)`	Entire digit range
`(1,1,5)`	One repeated digit
`(0,0,1000000000)`	Huge `k`, answer remains zero
`(0,9,2)`	All possible two-digit strings
`(3,7,1)`	Simple arithmetic-range check
`(0,9,1000000000)`	Performance stress test

Edge Cases

Only One Allowed Digit

When l = r, every position has exactly one valid choice. A common mistake is to continue reasoning as though multiple combinations exist. In this case m = 1, so m^(k-1) = 1, and the formula correctly reduces to the value of the single repeated-digit number.

Leading Zeros Are Allowed

Many digit DP or combinatorial problems forbid leading zeros. This problem explicitly allows them whenever 0 belongs to the digit range. For example, 000, 001, and 010 are all valid. The contribution-based derivation naturally handles this because every position is treated identically, including the most significant digit.

Extremely Large k

The value of k can be as large as 10^9. Any algorithm that loops through positions or builds the geometric series term by term will time out. The implementation uses modular exponentiation and the closed-form geometric-series formula, reducing the running time to O(log k).

Range Contains Only Zero

When l = r = 0, every generated digit string evaluates to zero regardless of length. The formula correctly produces zero because the digit sum S equals zero, making the final product zero.

Full Digit Range

When l = 0 and r = 9, there are 10^k generated digit strings. Explicit enumeration becomes impossible almost immediately. The combinatorial formula remains efficient because it depends only on modular exponentiation and not on the number of generated strings.