Skip to content

3871. Count Commas in Range II

SourceWeekly Contest 493 Q2DifficultyMediumRating1380

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:

Input: n = 1002

Output: 3

Explanation:

The numbers "1,000", "1,001", and "1,002" each contain one comma, giving a total of 3.

Example 2:

Input: n = 998

Output: 0

Explanation:

​​​​​​​All numbers from 1 to 998 have fewer than four digits. Therefore, no commas are used.

 

Constraints:

  • 1 <= n <= 1015

Solutions

Solution 1: Mathematics

Thinking

The same comma count, now with \(n \le 10^{15}\), so a number may contain several commas.

Each time a threshold \(10^{3t}\) is crossed, every later integer gains one more comma.

Start from \(x=1000\), multiply by \(1000\), and add \(n-x+1\) until \(x>n\).

The loop runs \(O(\log_{1000} n)\) times.

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