3870. Count Commas in Range
Problem Description
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:
- A comma is inserted after every three digits from the right.
- Numbers with fewer than 4 digits contain no commas.
In simple terms, this problem asks you to count how many commas appear in total when you write out every number from 1 to n, formatting each one the way we normally write large numbers (for example, 1,000 or 12,345).
The key observations are:
- Any number from
1to999has at most 3 digits, so it contains no commas. - A number with 4, 5, or 6 digits (from
1,000up to999,999) gets exactly one comma inserted after the first three digits from the right.
So for each number in the range [1, n], you simply add up how many commas that single number needs, and return the grand total across all of them.
How We Pick the Algorithm
Why Math / Bit Manipulation?
This problem maps to Math / Bit Manipulation through a short path in the full flowchart.
Closed-form formula max(0, n - 999) derived from the observation that only numbers >= 1000 have commas.
Open in FlowchartIntuition
The first thing to notice is that the number of commas in a single number depends only on how many digits it has. Numbers with fewer than 4 digits have no commas, while numbers with 4 to 6 digits have exactly one comma.
This suggests we should split the range [1, n] into two groups based on this behavior:
- The numbers from
1to999each contribute0commas. So ifnis999or smaller, the total is simply0. - The numbers from
1000onward each contribute exactly1comma. Since the constraint keepsnwithin[1, 10^5], every number that is at least1000falls in the 4-to-6 digit range and therefore has precisely one comma.
From here, counting becomes easy. When n >= 1000, we just need to count how many integers lie in the range [1000, n]. That count is n - 1000 + 1 = n - 999, and each of those contributes one comma, so the total number of commas is also n - 999.
Putting both cases together, the answer is 0 when n <= 999 and n - 999 when n >= 1000. These two cases collapse neatly into a single expression: max(0, n - 999). The max automatically handles the small-n case, since n - 999 becomes negative there and gets clamped to 0.
Pattern Learn more about Math patterns.
Solution Approach
Solution 1: Brain Teaser
Numbers from 1 to 999 contain no commas, so when n is less than or equal to 999, the answer is 0.
Since the range of n is [1, 10^5], when n is greater than or equal to 1000, each number contains exactly one comma, so the answer is n - 999.
Therefore, the answer is max(0, n - 999).
The implementation is a single line that directly returns this expression:
class Solution:
def countCommas(self, n: int) -> int:
return max(0, n - 999)
There is no need for any loops or data structures here. The max function elegantly merges the two cases into one:
- When
n <= 999, the valuen - 999is0or negative, somaxreturns0. - When
n >= 1000, the valuen - 999is positive and equals the count of numbers in[1000, n], each contributing exactly one comma.
The time complexity is O(1) and the space complexity is O(1), since the answer is computed with a constant amount of arithmetic regardless of the size of n.
Example Walkthrough
Let's trace through the solution approach using a small example with n = 1002.
Step 1: Identify which numbers contribute commas
We need to count commas across all numbers from 1 to 1002. According to our key observation, the numbers split into two groups:
- Numbers
1through999: each has at most 3 digits, so each contributes 0 commas. - Numbers
1000through1002: each has 4 digits, so each gets exactly one comma.
Step 2: Count commas from the first group (1 to 999)
Every number here is written without a comma:
1, 2, 3, ..., 999 → 0 commas total
So this entire group contributes nothing.
Step 3: Count commas from the second group (1000 to 1002)
Each of these is written with one comma:
1,000 → 1 comma 1,001 → 1 comma 1,002 → 1 comma
That's 3 numbers, each contributing one comma, for a total of 3 commas.
Step 4: Apply the formula
Instead of listing them out, we use the direct expression max(0, n - 999):
max(0, 1002 - 999) = max(0, 3) = 3
This matches our manual count exactly.
Step 5: Verify the small-n case (clamping in action)
To confirm the max handles small inputs, try n = 500:
max(0, 500 - 999) = max(0, -499) = 0
Since all numbers from 1 to 500 have fewer than 4 digits, the answer is correctly 0. The max clamps the negative result back to zero, merging both cases into one clean formula.
Solution Implementation
1class Solution:
2 def countCommas(self, n: int) -> int:
3 # Returns the difference between n and 999, clamped at a minimum of 0.
4 # Note: this preserves the original logic exactly as given.
5 return max(0, n - 999)
6```
7
8## Version 2: Corrected Logic (What the Name Suggests)
9
10If the goal is to genuinely **count the commas** in the formatted representation of an integer (one comma per group of three digits), the logic should be based on the number of digits:
11
12```python3
13class Solution:
14 def count_commas(self, n: int) -> int:
15 # Count the number of commas used when grouping digits in threes.
16 # For a number with d digits, the comma count is (d - 1) // 3.
17 # Work with the absolute value so negative numbers are handled correctly.
18 num_digits = len(str(abs(n)))
19 return (num_digits - 1) // 3
201class Solution {
2 /**
3 * Returns the difference between n and 999 when n exceeds 999,
4 * otherwise returns 0.
5 *
6 * Note: Despite the method name, this does not compute the number of
7 * thousands-separator commas in n's formatted representation. It simply
8 * computes max(0, n - 999).
9 *
10 * @param n the input integer value
11 * @return max(0, n - 999)
12 */
13 public int countCommas(int n) {
14 // If n is greater than 999, return n - 999; otherwise clamp the result to 0.
15 return Math.max(0, n - 999);
16 }
17}
18```
19
20**Alternative perspective:** If the intent was truly to count the thousands-separator commas in a number, the correct implementation would differ significantly. Here is that version for comparison:
21
22```java
23class Solution {
24 /**
25 * Counts the number of thousands-separator commas in the formatted
26 * representation of n (e.g., 1000000 -> "1,000,000" -> 2 commas).
27 *
28 * @param n the non-negative input integer
29 * @return the number of commas in the grouped representation of n
30 */
31 public int countCommas(int n) {
32 // Numbers below 1000 have no commas.
33 if (n < 1000) {
34 return 0;
35 }
36 // Count how many groups of three digits exist beyond the first group.
37 int commaCount = 0;
38 while (n >= 1000) {
39 n /= 1000; // Remove the last group of three digits.
40 commaCount++; // Each removed group corresponds to one comma.
41 }
42 return commaCount;
43 }
44}
451class Solution {
2public:
3 // Returns the count based on how much n exceeds 999.
4 // If n is 999 or less, the result is 0; otherwise it is n - 999.
5 int countCommas(int n) {
6 // Compute the difference between n and 999.
7 // Use max with 0 to ensure the result is never negative.
8 return std::max(0, n - 999);
9 }
10};
111/**
2 * Returns 0 when the input is at most 999;
3 * otherwise returns the amount by which the input exceeds 999.
4 *
5 * @param value - The input number to evaluate.
6 * @returns The non-negative difference between the input and 999.
7 */
8function countCommas(value: number): number {
9 // Threshold below which the result is clamped to zero.
10 const threshold: number = 999;
11
12 // Compute how much the input exceeds the threshold.
13 const difference: number = value - threshold;
14
15 // Clamp the result so it never drops below zero.
16 return Math.max(0, difference);
17}
18Time and Space Complexity
-
Time Complexity:
O(1). The function performs a single subtractionn - 999followed by a comparison viamax(0, ...). Both operations execute in constant time regardless of the input valuen, so the overall time complexity isO(1). -
Space Complexity:
O(1). The function uses only a fixed amount of extra space to compute and return the result, without allocating any additional data structures that scale with the input. Therefore, the space complexity isO(1).
Pattern Learn more about how to find time and space complexity quickly.
Common Pitfalls
Pitfall 1: Misreading the Problem as "Commas in a Single Number"
The most common mistake is confusing two completely different questions:
- Sum of commas across the whole range
[1, n](what this problem actually asks). - Commas in the single formatted number
n(what the method namecountCommasmisleadingly suggests).
Because the constraint guarantees n <= 10^5, every number in the range has at most one comma. This makes the per-number contribution either 0 (for 1–999) or 1 (for 1000–n). People who mentally map "count commas" to a single number often write:
# WRONG for this problem: counts commas in ONE number, not the whole range
return (len(str(n)) - 1) // 3
For n = 1000 this returns 1, but the correct answer is 1 only by coincidence. For n = 2000 it still returns 1, while the true answer is 1001 (numbers 1000 through 2000 each contribute one comma). Always confirm whether you are summing across a range or evaluating a single value.
Pitfall 2: Off-by-One When Counting [1000, n]
When deriving n - 999, it is tempting to write n - 1000 instead, reasoning "subtract the first number that has a comma." That undercounts by one because the range [1000, n] is inclusive on both ends:
# WRONG: drops the number 1000 itself
return max(0, n - 1000)
The correct count of integers in [1000, n] is n - 1000 + 1 = n - 999. A quick sanity check with the smallest commafied value catches this: for n = 1000, exactly one number has a comma, so the answer must be 1, and 1000 - 999 = 1 ✓, whereas 1000 - 1000 = 0 ✗.
Pitfall 3: Forgetting to Clamp the Lower Bound
Returning the raw expression without max(0, ...) produces negative results for small inputs:
# WRONG: returns negative values for n <= 999 return n - 999 # e.g., n = 5 -> -994
Any input from 1 to 999 should yield 0. Wrapping the expression in max(0, ...) (or an explicit if n < 1000: return 0) merges the two cases cleanly and guards against negatives.
Pitfall 4: Assuming the Pattern Holds Beyond the Constraints
The one-line formula max(0, n - 999) relies on the guarantee that n <= 10^5, so no number ever needs a second comma. If the constraints were relaxed (e.g., n up to 10^9), numbers ≥ 1,000,000 would each contribute two commas, and ≥ 1,000,000,000 would contribute three. The shortcut would then silently undercount.
Robust solution that works for any range by summing per-number comma counts in digit-group bands:
class Solution:
def countCommas(self, n: int) -> int:
if n < 1000:
return 0
total = 0
# Each band [10^(3k), 10^(3(k+1)) - 1] contributes k commas per number.
# Walk thresholds: 1000, 1_000_000, 1_000_000_000, ...
threshold = 1000
commas_per_number = 1
while threshold <= n:
upper = min(n, threshold * 1000 - 1)
total += (upper - threshold + 1) * commas_per_number
threshold *= 1000
commas_per_number += 1
return total
For n <= 10^5 this reduces to the same value as max(0, n - 999), but it remains correct if the limits ever grow. Match the chosen solution to the actual constraints, and prefer the general version when input bounds are uncertain.
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapHow does merge sort divide the problem into subproblems?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him
Want a Structured Path to Master System Design Too? Don’t Miss This!