418. Count Commas in Range II

Don't format 10^15 numbers one by one. Count commas by threshold instead: a number gains its first comma once it reaches 1,000 (4 digits), its second once it reaches 1,000,000 (7 digits), and its k-th once it reaches 1000^k. Every integer in [1000^k, n] contributes one comma at band k, so sum each band size (n - p + 1) over the thresholds p <= n.

Idea

With n up to 10^15, writing out and scanning every number is far too slow. The trick is to count commas by the boundary each number crosses, not 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. There are only about log_1000(n) such thresholds (at most 5 for n <= 10^15), so the whole computation is a handful of steps.

Handling the size

n can reach 10^15, which overflows a 32-bit integer, and the answer can reach roughly 4 * 10^15. Read n as a 64-bit integer (long in Java, arbitrary precision in Python) and return the answer as a string.

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 (as a string).

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 (at most 5 for n <= 10^15).
• Space: O(1).

class Solution {
    public String countCommas(String n) {
        long num = Long.parseLong(n.trim());
        long total = 0;
        long p = 1000;
        while (p <= num) {
            total += num - p + 1;
            p *= 1000;
        }
        return Long.toString(total);
    }
}