BigO Lab

Posted on Mar 15

Count Commas in Range - LeetCode-3870 Solution

#algorithms #python #leetcode #dsa

Today we're looking at Count Commas in Range. It's a pretty interesting problem that can easily trick you into writing a slow solution, especially once the constraints get big.

Let's break it down.

The Problem

Problem Link

We're given an integer n. We need to figure out the total number of commas used when writing all integers from 1 to n in standard format.

999 → 0 commas
1,000 → 1 comma
1,000,000 → 2 commas

We just return the total sum of all those commas.

Example 1:

Input:  n = 1000
Output: 1

Example 2:

Input:  n = 1000000
Output: 2998001

Brute Force

The most obvious way is to just loop through every number from 1 to n, count its commas, and add to a running total.

def countCommas(n: int) -> int:
    total = 0
    for i in range(1, n + 1):
        digits = len(str(i))
        total += (digits - 1) // 3
    return total

Does that work? Technically, yes.

But look at the constraints. If n goes up to 10^15, an O(n) solution is way too slow. Time Limit Exceeded. We need a math approach.

Intuition

Instead of iterating through numbers and asking "how many commas does this number have?", let's flip the question.

Think about the comma thresholds:

The first comma appears at 1,000. So every number from 1,000 to n contributes at least 1 comma.
The second comma appears at 1,000,000. So every number from 1,000,000 to n contributes 1 more comma.
The third comma appears at 1,000,000,000. Same idea.

So we don't need to look at individual numbers at all. We just ask: how many numbers crossed each threshold?

Count of numbers >= threshold in [1, n] is simply n - threshold + 1.

Walkthrough

Let's trace n = 1,500,000:

threshold = 1,000

n >= 1000 ✓
count = 1500000 - 1000 + 1 = 1,499,001

threshold = 1,000,000

n >= 1000000 ✓
count = 1500000 - 1000000 + 1 = 500,001

threshold = 1,000,000,000

n >= 1000000000 ✗  →  stop

Total = 1,499,001 + 500,001 = 1,999,002

Two iterations. Done.

Solution

Python

class Solution:
    def countCommas(self, n: int) -> int:
        total = 0
        threshold = 1000

        while n >= threshold:
            total += n - threshold + 1
            threshold *= 1000

        return total

JavaScript

var countCommas = function(n) {
    let total = 0;
    let threshold = 1000;

    while (n >= threshold) {
        total += n - threshold + 1;
        threshold *= 1000;
    }

    return total;
};

Java

class Solution {
    public long countCommas(long n) {
        long total = 0;
        long threshold = 1000;

        while (n >= threshold) {
            total += n - threshold + 1;
            threshold *= 1000;
        }

        return total;
    }
}

⚠️ Use long in Java. For n = 10^15 the result can exceed Integer.MAX_VALUE.

Verification

n = 1000:

threshold = 1000:    ✓  →  total += 1000 - 1000 + 1 = 1
threshold = 1000000: ✗  →  stop

Output: 1 ✓

n = 9999:

threshold = 1000:    ✓  →  total += 9999 - 1000 + 1 = 9000
threshold = 1000000: ✗  →  stop

Output: 9000 ✓

Numbers 1,000 through 9,999 — exactly 9,000 four-digit numbers, each with one comma. Makes sense.

Complexity

	Complexity	Notes
Time	O(log n)	Loop runs ~5 times even for n = 10^15
Space	O(1)	Just two variables

Common Mistakes

Off-by-one — count is n - threshold + 1, not n - threshold. Easy to miss.
Wrong starting threshold — start at 1000, not 100. Numbers like 100 don't get commas.
Integer overflow — in Java/C++, use long. Python handles big integers natively.

Key Takeaway

The pattern here is counting contributions layer by layer. Instead of iterating over every number, iterate over the boundaries.

You'll see this same pattern in:

Count digits in a range
Count integers with a specific digit count in [1, n]
Number of set bits across all integers from 1 to n

Whenever a problem asks you to count some property across all integers in [1, n], think thresholds first. The brute force loops over numbers. The optimal solution loops over boundaries.

Did anyone else get stuck trying to do this with string formatting, or was it just me? Let me know in the comments!

DEV Community