3871. Count Commas in Range II

Problem Overview

Commas appear at every three digits from the right.

Intuition

Commas appear at every three digits from the right. Crossing 1000 adds the first comma, crossing 1e6 adds a second, and so on. For each threshold x = 1000^k, every number from x through n contributes one more comma, so add n - x + 1.

Algorithm

1Initialize ans = 0 and x = 1000.
2While x is at most n, add n - x + 1 to ans.
3Multiply x by 1000 and repeat.
4Return ans as a long.

Example Walkthrough

Input: n = 1000000

1.At x = 1000: add 1000000 - 1000 + 1 numbers with at least one comma.
2.At x = 1000000: add 1 more for the second comma on 1000000 itself.
3.Next threshold exceeds n, so stop.

Output: 999002

Common Pitfalls

•n can reach 10^15, so use long for both n and the answer.
•Include the threshold itself with n - x + 1, not n - x.
•Unlike part I, max(0, n - 999) is wrong once a second comma layer appears.
•The loop runs only a few times because x grows by 1000x each step.

3871.cs

// Approach: Each power of 1000 adds one more comma for every number at or
// above that threshold. Sum (n - x + 1) for x = 1000, 1e6, 1e9, ... while x <= n.
// Complexity: O(log n) time and O(1) extra space.
public class Solution
{
    public long CountCommas(long n)
    {
        long ans = 0;
        for (long x = 1000; x <= n; x *= 1000)
            ans += n - x + 1;
        return ans;
    }
}

Was this solution helpful?