Sum of K-Digit Numbers in a Range solution and explanation
The problem
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
Approach overview
Problem Overview: Given a numeric range [L, R] and an integer K, compute the sum of all numbers inside the range that contain exactly K digits. The key observation: every K-digit number lies between 10^(K-1) and 10^K - 1.
Approach 1: Brute Force Range Scan (O(R - L) time, O(1) space)
Iterate through every number from L to R. For each value, determine its digit count by repeatedly dividing by 10 or converting to a string. If the digit length equals K, add the number to the running sum. This approach is straightforward but impractical when the range is large. It performs unnecessary checks for numbers whose digit lengths clearly cannot match K.
Approach 2: Math + Fast Power (O(log K) time, O(1) space)
A K-digit number must fall within the interval [10^(K-1), 10^K - 1]. Instead of scanning the entire range, compute the intersection of this interval with the given range [L, R]. Let start = max(L, 10^(K-1)) and end = min(R, 10^K - 1). If start > end, no valid numbers exist.
Otherwise, compute the sum of all integers from start to end using the arithmetic series formula:
sum = (count * (start + end)) / 2 where count = end - start + 1.
The only non‑constant operation is computing powers of ten. Use fast exponentiation to compute 10^(K-1) and 10^K efficiently in O(log K) time. This approach eliminates iteration over the range and relies purely on mathematical boundaries.
Conceptually this falls under number theory and combinatorics because the solution derives numeric constraints instead of enumerating candidates. Fast exponentiation is a classic divide and conquer technique used to compute powers efficiently.
Recommended for interviews: The math + fast power solution is the expected answer. Interviewers want to see you identify the numeric bounds of K-digit numbers and avoid iterating through the range. Mentioning the brute-force scan shows baseline understanding, but deriving the closed-form arithmetic sum demonstrates stronger problem-solving and mathematical reasoning.
Solution
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:
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 ansclass 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;
}
};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;
}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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Scan | O(R - L) | O(1) | Useful only for very small ranges or quick prototyping |
| Math + Fast Power | O(log K) | O(1) | Optimal solution for large ranges; avoids scanning numbers |
Frequently asked questions
Is Sum of K-Digit Numbers in a Range easy or hard?
The problem is typically classified as Hard because the efficient solution requires recognizing numeric boundaries and applying mathematical formulas instead of iterating through the range. Candidates who rely on brute force often fail large input constraints.
Sum of K-Digit Numbers in a Range Python/Java solution
Implement a fast power function to compute powers of 10, determine the overlap between [L, R] and [10^(K-1), 10^K - 1], then apply the arithmetic progression sum formula. The same logic works in Python, Java, C++, Go, and TypeScript with constant space.
How to solve Sum of K-Digit Numbers in a Range in O(log K)?
First compute the K-digit boundaries using fast exponentiation: low = 10^(K-1) and high = 10^K - 1. Intersect this interval with [L, R]. If the intersection exists, compute the sum using (count * (start + end)) / 2 where count = end - start + 1.
What is the best approach for Sum of K-Digit Numbers in a Range?
The optimal approach uses math with fast exponentiation. Compute the valid K-digit interval [10^(K-1), 10^K - 1], intersect it with the given range [L, R], then apply the arithmetic series formula to get the total sum. This avoids scanning the range and runs in O(log K) time with O(1) space.
Is Sum of K-Digit Numbers in a Range asked at Google/Amazon/Meta?
Problems involving digit ranges, mathematical bounds, and fast exponentiation appear frequently in interviews at companies like Google, Amazon, and Meta. They test number theory reasoning and the ability to replace brute force with mathematical formulas.
What data structure is used in Sum of K-Digit Numbers in a Range?
No complex data structure is required. The optimal solution relies on mathematical computation, arithmetic series formulas, and fast exponentiation, which is typically implemented using a divide and conquer power function.
What is the time complexity of Sum of K-Digit Numbers in a Range?
The optimal solution runs in O(log K) time due to fast power calculations for 10^(K-1) and 10^K. The rest of the work is constant-time arithmetic to compute the range intersection and series sum. Space complexity remains O(1).