Skip to content

3855. Sum of K-Digit Numbers in a Range

Description

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

Consider all possible integers consisting of exactly k digits, where each digit is chosen independently from the integer range [l, r] (inclusive). If 0 is included in the range, leading zeros are allowed.

Return an integer representing the sum of all such numbers.​​​​​​​ Since the answer may be very large, return it modulo 109 + 7.

Β 

Example 1:

Input: l = 1, r = 2, k = 2

Output: 66

Explanation:

  • All numbers formed using k = 2 digits in the range [1, 2] are 11, 12, 21, 22.
  • The total sum is 11 + 12 + 21 + 22 = 66.

Example 2:

Input: l = 0, r = 1, k = 3

Output: 444

Explanation:

  • All numbers formed using k = 3 digits in the range [0, 1] are 000, 001, 010, 011, 100, 101, 110, 111​​​​​​​.
  • These numbers without leading zeros are 0, 1, 10, 11, 100, 101, 110, 111.
  • The total sum is 444.

Example 3:

Input: l = 5, r = 5, k = 10

Output: 555555520

Explanation:​​​​​​​

  • 5555555555 is the only valid number consisting of k = 10 digits in the range [5, 5].
  • The total sum is 5555555555 % (109 + 7) = 555555520.

Β 

Constraints:

  • 0 <= l <= r <= 9
  • 1 <= k <= 109

Solutions

Solution 1: Math + Fast Power

We enumerate each digit \(x\) from the lowest position to the highest. Suppose the current position is the \(i\)-th digit (0-indexed), which contributes \(x \cdot 10^i\) to the number. The remaining \(k - 1\) digits each have \(r - l + 1\) choices, so the contribution of the current position is \(x \cdot 10^i \cdot (r - l + 1)^{k - 1}\). Since \(x\) ranges over \([l, r]\), the sum of all values of \(x\) is \(\frac{(l + r) \cdot (r - l + 1)}{2}\). Therefore, the total sum of all such numbers is:

\[ \begin{aligned} &\sum_{i = 0}^{k - 1} \frac{(l + r) \cdot (r - l + 1)}{2} \cdot (r - l + 1)^{k - 1} \cdot 10^i \\ = &\frac{(l + r) \cdot (r - l + 1)}{2} \cdot (r - l + 1)^{k - 1} \cdot \frac{10^k - 1}{9} \end{aligned} \]

Since \(k\) can be up to \(10^9\), we use fast power (binary exponentiation) to compute \((r - l + 1)^{k - 1}\) and \(10^k\). Division by \(9\) is handled using the modular inverse of \(9\) via Fermat's little theorem.

The time complexity is \(O(\log k)\) and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def sumOfNumbers(self, l: int, r: int, k: int) -> int:
        mod = 10**9 + 7

        n = r - l + 1

        # ((l + r) * (r - l + 1) // 2) % mod
        total = (l + r) * n // 2 % mod

        # pow(r - l + 1, k - 1, mod)
        part1 = pow(n % mod, k - 1, mod)

        # (pow(10, k, mod) - 1)
        part2 = (pow(10, k, mod) - 1) % mod

        # Fermat inverse of 9
        inv9 = pow(9, mod - 2, mod)

        ans = total
        ans = ans * part1 % mod
        ans = ans * part2 % mod
        ans = ans * inv9 % 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
class Solution {
    public int sumOfNumbers(int l, int r, int k) {
        final int mod = 1_000_000_007;

        long n = r - l + 1L;

        // ((l + r) * (r - l + 1) // 2) % mod
        long sum = (long) (l + r) * n / 2 % mod;

        // pow(r - l + 1, k - 1, mod)
        long part1 = qpow(n % mod, k - 1, mod);

        // (pow(10, k, mod) - 1)
        long part2 = (qpow(10, k, mod) - 1 + mod) % mod;

        // pow(9, mod - 2, mod)  (Fermat inverse of 9)
        long inv9 = qpow(9, mod - 2, mod);

        long ans = sum;
        ans = ans * part1 % mod;
        ans = ans * part2 % mod;
        ans = ans * inv9 % mod;

        return (int) ans;
    }

    private int qpow(long a, int n, int mod) {
        long ans = 1;
        a %= mod;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                ans = ans * a % mod;
            }
            a = a * a % mod;
        }
        return (int) 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
class Solution {
public:
    int sumOfNumbers(int l, int r, int k) {
        const int mod = 1'000'000'007;

        long long n = 1LL * r - l + 1;

        // ((l + r) * (r - l + 1) / 2) % mod
        long long sum = 1LL * (l + r) * n / 2 % mod;

        // pow(r - l + 1, k - 1, mod)
        long long part1 = qpow(n % mod, k - 1, mod);

        // (pow(10, k, mod) - 1)
        long long part2 = (qpow(10, k, mod) - 1 + mod) % mod;

        // Fermat inverse of 9
        long long inv9 = qpow(9, mod - 2, mod);

        long long ans = sum;
        ans = ans * part1 % mod;
        ans = ans * part2 % mod;
        ans = ans * inv9 % mod;

        return (int) ans;
    }

private:
    long long qpow(long long a, long long n, int mod) {
        long long ans = 1;
        a %= mod;
        while (n > 0) {
            if (n & 1) {
                ans = ans * a % mod;
            }
            a = a * a % mod;
            n >>= 1;
        }
        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
func sumOfNumbers(l int, r int, k int) int {
    const mod int64 = 1_000_000_007

    n := int64(r - l + 1)

    // ((l + r) * (r - l + 1) / 2) % mod
    sum := int64(l+r) * n / 2 % mod

    // pow(r - l + 1, k - 1, mod)
    part1 := qpow(n%mod, int64(k-1), mod)

    // (pow(10, k, mod) - 1)
    part2 := (qpow(10, int64(k), mod) - 1 + mod) % mod

    // Fermat inverse of 9
    inv9 := qpow(9, mod-2, mod)

    ans := sum
    ans = ans * part1 % mod
    ans = ans * part2 % mod
    ans = ans * inv9 % mod

    return int(ans)
}

func qpow(a int64, n int64, mod int64) int64 {
    a %= mod
    var ans int64 = 1
    for n > 0 {
        if n&1 == 1 {
            ans = ans * a % mod
        }
        a = a * a % mod
        n >>= 1
    }
    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
function sumOfNumbers(l: number, r: number, k: number): number {
    const mod = 1_000_000_007n;

    const n = BigInt(r - l + 1);

    // ((l + r) * (r - l + 1) / 2) % mod
    const sum = ((BigInt(l + r) * n) / 2n) % mod;

    // pow(r - l + 1, k - 1, mod)
    const part1 = qpow(n % mod, BigInt(k - 1), mod);

    // (pow(10, k, mod) - 1)
    const part2 = (qpow(10n, BigInt(k), mod) - 1n + mod) % mod;

    // Fermat inverse of 9
    const inv9 = qpow(9n, mod - 2n, mod);

    let ans = sum;
    ans = (ans * part1) % mod;
    ans = (ans * part2) % mod;
    ans = (ans * inv9) % mod;

    return Number(ans);
}

function qpow(a: bigint, n: bigint, mod: bigint): bigint {
    a %= mod;
    let ans = 1n;
    while (n > 0n) {
        if ((n & 1n) === 1n) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        n >>= 1n;
    }
    return ans;
}

Comments