3871. Count Commas in Range II

Description

You are given an integer n.

Return the total number of commas used when writing all integers from [1, n] (inclusive) in standard number formatting.

In standard formatting:

• A comma is inserted after every three digits from the right.
• Numbers with fewer than 4 digits contain no commas.

Example 1:

Example 2:

Constraints:

• 1 <= n <= 1015

Solutions

Solution 1: Mathematics

Based on the problem description, we can observe the following pattern:

• Numbers in the range [1, 999] contain no commas;
• Numbers in the range [1,000, 999,999] contain one comma;
• Numbers in the range [1,000,000, 999,999,999] contain two commas;
• And so on.

Therefore, we can start from \(x = 1000\) and multiply \(x\) by 1000 each time until \(x\) exceeds \(n\). In each iteration, there are \(n - x + 1\) numbers that newly gain one comma, and we accumulate their count into the answer.

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8

class Solution:
    def countCommas(self, n: int) -> int:
        ans = 0
        x = 1000
        while x <= n:
            ans += n - x + 1
            x *= 1000
        return ans

1
2
3
4
5
6
7
8
9

class Solution {
    public long countCommas(long n) {
        long ans = 0;
        for (long x = 1000; x <= n; x *= 1000) {
            ans += n - x + 1;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    long long countCommas(long long n) {
        long long ans = 0;
        for (long long x = 1000; x <= n; x *= 1000) {
            ans += n - x + 1;
        }
        return ans;
    }
};

1
2
3
4
5
6

func countCommas(n int64) (ans int64) {
    for x := int64(1000); x <= n; x *= 1000 {
        ans += n - x + 1
    }
    return
}

1
2
3
4
5
6
7

function countCommas(n: number): number {
    let ans = 0;
    for (let x = 1000; x <= n; x *= 1000) {
        ans += n - x + 1;
    }
    return ans;
}

Comments