LeetCode Problem 3871

Difficulty: 🟡 Medium
Topics: Math

Solution

LeetCode 3871 - Count Commas in Range II

Problem Understanding

The problem asks us to count the total number of commas that appear when writing every integer from 1 through n using standard comma-separated number formatting.

In standard formatting, commas are inserted every three digits from the right:

• 1 through 999 contain no commas.
• 1,000 through 999,999 contain one comma each.
• 1,000,000 through 999,999,999 contain two commas each.
• 1,000,000,000 through 999,999,999,999 contain three commas each.
• And so on.

The input consists of a single integer n. The output should be the total number of commas appearing across all formatted numbers in the inclusive range [1, n].

The constraint 1 <= n <= 10^15 is extremely important. Since n can be as large as one quadrillion, iterating through every number and formatting it individually would be far too slow. A solution must work in logarithmic time relative to the size of n.

Several edge cases are worth identifying immediately:

• Values below 1000 should always return 0.
• Values exactly at comma boundaries such as 1000, 1,000,000, and 1,000,000,000 are easy places for off-by-one mistakes.
• Very large values near 10^15 require careful counting without overflow.
• Numbers with multiple commas contribute more than one comma each, so we cannot simply count how many numbers contain commas.

Approaches

Brute Force

A straightforward solution would iterate through every number from 1 to n.

For each number:

1. Determine how many commas its formatted representation contains.
2. Add that count to the answer.

The number of commas in an integer with d digits is:

(d - 1) // 3

For example:

• 123 → 0 commas
• 1,234 → 1 comma
• 1,234,567 → 2 commas

This approach is correct because it explicitly computes the contribution of every number.

However, its running time is O(n), which is completely infeasible when n can be as large as 10^15.

Key Insight

Instead of examining numbers individually, we can count entire ranges at once.

Observe that all numbers in a given digit range contain the same number of commas:

Range	Commas per Number
1 to 999	0
1,000 to 999,999	1
1,000,000 to 999,999,999	2
1,000,000,000 to 999,999,999,999	3
...	...

For each comma count k:

• Numbers from 10^(3k) onward contain at least k commas.
• Every number in that interval contributes exactly k commas until the next boundary.

Therefore, we can count how many numbers fall into each comma group and multiply by the number of commas contributed by each number.

Since the largest possible value is 10^15, there are only a handful of comma groups, making the solution extremely efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Examine every number individually
Optimal	O(log n)	O(1)	Count contributions by comma ranges

Algorithm Walkthrough

1. Initialize answer = 0.
2. Let commas = 1. Numbers with one comma begin at 10^3 = 1000.
3. For each comma count:

• Compute the first number in this group:

start = 10^(3 * commas)

• If start > n, no numbers in this group exist, so stop.

4. Compute how many numbers from this group appear in [1, n].

Since every number from start through n contains at least commas commas:

count = n - start + 1

5. Every one of those numbers contributes one occurrence of the current comma position, so add:

answer += count

6. Increase commas by one and repeat.
7. Return answer.

Why it works

Consider a comma position individually.

• Every number from 1000 onward contains the first comma.
• Every number from 1,000,000 onward contains the second comma.
• Every number from 1,000,000,000 onward contains the third comma.

Therefore, instead of counting commas per number, we count how many numbers contain each comma position. Summing these contributions over all comma positions counts every comma exactly once, producing the correct total.

Python Solution

class Solution:
    def countCommas(self, n: int) -> int:
        answer = 0
        commas = 1

        while True:
            start = 10 ** (3 * commas)

            if start > n:
                break

            answer += n - start + 1
            commas += 1

        return answer

The implementation directly follows the mathematical observation.

The variable commas represents a comma position. For example:

• commas = 1 corresponds to the comma appearing in numbers >= 1000.
• commas = 2 corresponds to the comma appearing in numbers >= 1,000,000.

For each comma position, we compute the first number that contains it. Every number from that point through n contributes one occurrence of that comma, so the contribution is simply n - start + 1.

Because each iteration handles an entire comma position rather than individual numbers, only a few iterations are required.

Go Solution

func countCommas(n int64) int64 {
	var answer int64 = 0
	var commas int64 = 1

	for {
		start := int64(1)
		for i := int64(0); i < 3*commas; i++ {
			start *= 10
		}

		if start > n {
			break
		}

		answer += n - start + 1
		commas++
	}

	return answer
}

The Go version uses int64, which is sufficient because the maximum input is 10^15.

The logic is identical to the Python solution. The only notable difference is that Go does not have a built in integer exponentiation operator, so 10^(3*commas) is computed using a small loop.

Worked Examples

Example 1

Input:

n = 1002

Iteration Details

commas	start	contribution	answer
1	1000	1002 - 1000 + 1 = 3	3
2	1000000	stop	3

Result:

3

The numbers are:

1,000
1,001
1,002

Each contains one comma.

Example 2

Input:

n = 998

Iteration Details

commas	start	Action
1	1000	stop immediately

Result:

0

No number in the range contains a comma.

Additional Example

Input:

n = 1000000

Iteration Details

commas	start	contribution
1	1000	1000000 - 1000 + 1 = 999001
2	1000000	1000000 - 1000000 + 1 = 1
3	1000000000	stop

Total:

999001 + 1 = 999002

The number 1,000,000 contributes two commas, which is why the second group contributes one additional comma.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	One iteration per comma position
Space	O(1)	Only a few variables are used

The number of iterations equals the number of comma positions that can appear in n. Since each comma corresponds to three additional digits, the loop runs roughly digits(n) / 3 times. For n ≤ 10^15, this is at most five iterations, making the algorithm effectively constant time.

Test Cases

s = Solution()

assert s.countCommas(1) == 0          # smallest input
assert s.countCommas(998) == 0        # below first comma boundary
assert s.countCommas(999) == 0        # last number without commas
assert s.countCommas(1000) == 1       # first number with one comma
assert s.countCommas(1002) == 3       # example 1
assert s.countCommas(1999) == 1000    # all numbers 1000..1999 contribute one comma

assert s.countCommas(999999) == 999000       # all six-digit and four-digit numbers
assert s.countCommas(1000000) == 999002      # first number with two commas

assert s.countCommas(1000001) == 999004      # two numbers with two commas

assert s.countCommas(999999999) == (
    (999999999 - 1000 + 1) +
    (999999999 - 1000000 + 1)
)  # complete one-comma and two-comma ranges

assert s.countCommas(10**15) > 0     # upper constraint stress test

Test Case Summary

Test	Why
1	Smallest valid input
998	Below first comma threshold
999	Largest value with no commas
1000	First value containing a comma
1002	Official example
1999	Simple one-comma range
999999	End of one-comma region
1000000	First value with two commas
1000001	Verifies multiple two-comma values
999999999	Large multi-group calculation
10^15	Maximum constraint stress test

Edge Cases

Numbers Smaller Than 1000

Values from 1 through 999 contain no commas. A common bug is accidentally counting commas starting at 100 or using an incorrect threshold. The implementation correctly checks whether 10^3 is less than or equal to n. If not, the loop never executes and the answer remains 0.

Exact Power of One Thousand

Values such as 1000, 1,000,000, and 1,000,000,000 are common sources of off by one errors. For example, 1,000,000 contains two commas and must contribute to both the one-comma and two-comma counts. The formula n - start + 1 includes the boundary value itself, ensuring these numbers are counted correctly.

Very Large Inputs

The upper bound is 10^15, making brute force impossible. An implementation that loops through every number would require trillions of iterations. The optimal solution only iterates once per comma position, which is at most five iterations for the given constraints, so it easily handles the maximum input size.

Numbers With Multiple Commas

A subtle mistake is counting only how many numbers contain commas. For example, 1,000,000 contains two commas, not one. The algorithm avoids this issue by counting each comma position independently. A number with three commas is automatically counted once in the first-comma group, once in the second-comma group, and once in the third-comma group, exactly matching its total comma count.