417. Count Commas in Range

Instead of formatting every number, count commas by threshold. A number gets its first comma once it reaches 1,000 (4 digits), a second once it reaches 1,000,000 (7 digits), and so on. Every integer in [1000, n] contributes one comma, every integer in [1000000, n] contributes another, etc. Sum those band sizes.

Idea

Writing out each of the up-to-10^5 numbers and counting their commas works, but there is a cleaner way: count commas by the boundary each number crosses rather than number-by-number.

A number picks up:

• its 1st comma once it has 4 digits, i.e. once it is >= 1000,
• its 2nd comma once it has 7 digits, i.e. once it is >= 1,000,000,
• its k-th comma once it is >= 1000^k.

So the total number of commas is the sum, over each threshold p = 1000, 1000000, ..., of how many numbers in [1, n] are >= p — which is simply n - p + 1 for each threshold p <= n.

Algorithm

1. total = 0, p = 1000.
2. While p <= n: add n - p + 1 to total, then multiply p by 1000 to move to the next digit-group boundary.
3. Return total.

Worked example: n = 1002

• Threshold p = 1000 (p <= 1002): the numbers 1000, 1001, 1002 are all >= 1000, that's 1002 - 1000 + 1 = 3 numbers, each with one comma → total = 3.
• Threshold p = 1,000,000 (p > 1002): stop.

Result: 3 commas — matching "1,000", "1,001", "1,002".

For n = 998 the very first threshold 1000 already exceeds n, so the loop never runs and the answer is 0.

Complexity

• Time: O(log n) — one step per digit-group boundary below n.
• Space: O(1).

class Solution {
    public int countCommas(int n) {
        long total = 0;
        long p = 1000;
        while (p <= n) {
            total += n - p + 1;
            p *= 1000;
        }
        return (int) total;
    }
}