3871 LeetCode daily problem solution

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

We cannot use the formula from 3870 here because, with n <= 1015, numbers can contain multiple commas.

It is more convenient to count not each number separately, but each comma level.

Every number from 1,000 to n has at least one comma. So the first comma contributes:
n - 1000 + 1.

Every number from 1,000,000 to n has one additional comma:
n - 1,000,000 + 1.

Then there is another comma for every number from 1,000,000,000 to n, and so on.

Since a new comma appears every three additional digits we have start *= 1000.

It is important to understand that with the specific constraint n <= 1015, the loop runs at most 5 times. So, formally, for this problem we can even write:

Time complexity: O(1)
Space complexity: O(1)

but using O(log n) for Time complexity better shows how the algorithm scales.

Time complexity: O(log n)
Space complexity: O(1)

LeetCode 3871 C++ solution

class Solution {
public:
  long long countCommas(long long n) {
    long long result = 0;

    for(long long start = 1000; start <= n; start *= 1000) 
      result += n - start + 1;

    return result;
  }
};

LeetCode 3871 Java solution

class Solution {
  public long countCommas(long n) {
    long result = 0;

    for(long start = 1000; start <= n; start *= 1000)
      result += n - start + 1;

    return result;
  }
}

LeetCode 3871 JavaScript solution

var countCommas = function(n) {
  let result = 0;

  for(let start = 1000; start <= n; start *= 1000)
    result += n - start + 1;

  return result;
};

LeetCode 3871 TypeScript solution

function countCommas(n: number): number {
  let result = 0;

  for(let start = 1000; start <= n; start *= 1000)
    result += n - start + 1;

  return result;
};

LeetCode 3871 Python solution

class Solution:
  def countCommas(self, n: int) -> int:
    result = 0
    start = 1000

    while start <= n:
      result += n - start + 1
      start *= 1000

    return result