Welcome to Subscribe On Youtube
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 = 2digits in the range[1, 2]are11, 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 = 3digits in the range[0, 1]are000, 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 = 10digits in the range[5, 5]. - The total sum is
5555555555 % (109 + 7) = 555555520.
Constraints:
0 <= l <= r <= 91 <= 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)$.
-
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; } } -
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; } }; -
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 -
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 } -
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; }