You are given an integer n.
Return the total number of commas used when writing all integers from [1, n] (inclusive) in standard number formatting.
In standard formatting:
Example 1:
Input: n = 1002
Output: 3
Explanation:
The numbers "1,000", "1,001", and "1,002" each contain one comma, giving a total of 3.
Example 2:
Input: n = 998
Output: 0
Explanation:
All numbers from 1 to 998 have fewer than four digits. Therefore, no commas are used.
Constraints:
1 <= n <= 1015Problem Overview: Given a range [l, r], count how many comma separators appear when every integer in that range is written using standard thousands formatting (e.g., 1,234, 12,345,678). Numbers gain one comma for every group of three digits after the first group.
Approach 1: Direct Simulation (O(n log n) time, O(1) space)
The most straightforward method is to iterate from l to r, compute the digit length of each number, and derive how many commas it contains. A number with d digits contributes floor((d-1)/3) commas. For example, 4–6 digit numbers have one comma, 7–9 digit numbers have two. During iteration you compute the digit count (using log10 or string length) and accumulate the comma contribution. This works for small ranges but becomes too slow if r - l is large because every number is processed individually.
Approach 2: Mathematical Range Counting (O(log10 r) time, O(1) space)
A more efficient approach counts numbers by digit groups instead of iterating through the range. Commas appear when numbers cross powers of 10^3. For example, numbers from 1,000 to 999,999 contain exactly one comma, while numbers from 1,000,000 to 999,999,999 contain two. For each comma level k, determine the interval [10^{3k}, 10^{3(k+1)} - 1]. Intersect that interval with the query range [l, r] and count how many numbers fall inside it. Each of those numbers contributes k commas. Summing these contributions across all possible k values produces the total. Since the number of comma levels is small (at most ~6 for 64-bit numbers), the algorithm runs in logarithmic time.
This technique relies on simple digit math and range intersection rather than iteration. Problems like this are classic applications of math reasoning combined with digit-length analysis. You treat the number line as blocks defined by powers of ten and compute contributions per block.
Recommended for interviews: Interviewers expect the mathematical counting approach. Starting with the brute-force idea shows understanding of how commas relate to digit length. The optimized method demonstrates the real skill: recognizing numeric thresholds (10^3, 10^6, 10^9) and aggregating counts using mathematical range analysis instead of iterating through every number.
Based on the problem description, we can observe the following pattern:
Therefore, we can start from x = 1000 and multiply x by 1000 each time until x exceeds n. In each iteration, there are n - x + 1 numbers that newly gain one comma, and we accumulate their count into the answer.
The time complexity is O(log n), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n log n) | O(1) | Small ranges where iterating from l to r is feasible |
| Mathematical Range Counting | O(log10 r) | O(1) | Large ranges where counting by digit thresholds is required |
Leetcode Weekly Contest 493 Q2. Count Commas in Range II #python #dsa • ADevOpsBeginner • 303 views views
Watch 8 more video solutions →Practice Count Commas in Range II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor