Welcome to Subscribe On Youtube
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:
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
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)$.
-
class Solution { public long countCommas(long n) { long ans = 0; for (long x = 1000; x <= n; x *= 1000) { ans += n - x + 1; } return ans; } } -
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; } }; -
class Solution: def countCommas(self, n: int) -> int: ans = 0 x = 1000 while x <= n: ans += n - x + 1 x *= 1000 return ans -
func countCommas(n int64) (ans int64) { for x := int64(1000); x <= n; x *= 1000 { ans += n - x + 1 } return } -
function countCommas(n: number): number { let ans = 0; for (let x = 1000; x <= n; x *= 1000) { ans += n - x + 1; } return ans; }