Skip to main content
Talentd

Sum of K-Digit Numbers in a Range - Solution & Explanation

HardMathDivide and ConquerCombinatoricsNumber Theory12 min read
Practice this problem

Problem Statement

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

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)$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Range ScanO(R - L)O(1)Useful only for very small ranges or quick prototyping
Math + Fast PowerO(log K)O(1)Optimal solution for large ranges; avoids scanning numbers

Video Solution

Leetcode 3855 | Sum of K-Digit Numbers in a Range | Leetcode biweekly contest 177 • CodeWithMeGuys • 327 views views

Watch 1 more video solutions →

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).

Ready to solve this problem?

Practice Sum of K-Digit Numbers in a Range with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer