Facebook Pixel

3870. Count Commas in Range

EasyMath
LeetCode ↗

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 1 to 999 has at most 3 digits, so it contains no commas.
  • A number with 4, 5, or 6 digits (from 1,000 up to 999,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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

Bitmanipulationor math?yesNumbertheory?noMath / BitManipulation

Closed-form formula max(0, n - 999) derived from the observation that only numbers >= 1000 have commas.

Open in Flowchart

Intuition

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 1 to 999 each contribute 0 commas. So if n is 999 or smaller, the total is simply 0.
  • The numbers from 1000 onward each contribute exactly 1 comma. Since the constraint keeps n within [1, 10^5], every number that is at least 1000 falls 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 value n - 999 is 0 or negative, so max returns 0.
  • When n >= 1000, the value n - 999 is 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 1 through 999: each has at most 3 digits, so each contributes 0 commas.
  • Numbers 1000 through 1002: 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, ..., 9990 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,0001 comma
1,0011 comma
1,0021 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
20
1class 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}
45
1class 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};
11
1/**
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}
18

Time and Space Complexity

  • Time Complexity: O(1). The function performs a single subtraction n - 999 followed by a comparison via max(0, ...). Both operations execute in constant time regardless of the input value n, so the overall time complexity is O(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 is O(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:

  1. Sum of commas across the whole range [1, n] (what this problem actually asks).
  2. Commas in the single formatted number n (what the method name countCommas misleadingly 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 1999) or 1 (for 1000n). 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 Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How does merge sort divide the problem into subproblems?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More