Watch 3 video solutions for Sum of K-Digit Numbers in a Range, a hard level problem involving Math, Divide and Conquer, Combinatorics. This walkthrough by CodeWithMeGuys has 285 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
k = 2 digits in the range [1, 2] are 11, 12, 21, 22.11 + 12 + 21 + 22 = 66.Example 2:
Input: l = 0, r = 1, k = 3
Output: 444
Explanation:
k = 3 digits in the range [0, 1] are 000, 001, 010, 011, 100, 101, 110, 111.0, 1, 10, 11, 100, 101, 110, 111.Example 3:
Input: l = 5, r = 5, k = 10
Output: 555555520
Explanation:
k = 10 digits in the range [5, 5].5555555555 % (109 + 7) = 555555520.
Constraints:
0 <= l <= r <= 91 <= k <= 109Problem 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.
| 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 |