Count Commas in Range

Difficulty: Easy | Acceptance: 68.90% | Paid: No Topics: Math

Given two integers lower and upper, return the total number of commas used when writing all numbers from lower to upper (inclusive) with standard thousand separators (commas are placed after every three digits from the right).

Examples

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 <= lower <= upper <= 10^9

Approach 1: Brute Force

Intuition Iterate through each number in the range and count the commas in each number individually.

Steps

• For each number from lower to upper:
  • Count the number of digits
  • Calculate commas as floor((digits - 1) / 3)
  • Add to total

class Solution:
    def countCommas(self, lower: int, upper: int) -> int:
        def count_commas_in_number(n):
            return max(0, (len(str(n)) - 1) // 3)
        
        total = 0
        for i in range(lower, upper + 1):
            total += count_commas_in_number(i)
        return total

Complexity

• Time: O((upper - lower + 1) × log(upper))
• Space: O(1)
• Notes: Simple but slow for large ranges

Approach 2: Mathematical Formula

Intuition Use prefix sums and mathematical grouping to count commas efficiently without iterating through each number.

Steps

• Define a function to count commas from 1 to n
• For each comma level k (1 comma, 2 commas, etc.):
  • Find the range of numbers with exactly k commas
  • Count how many of those numbers are ≤ n
  • Add k × count to total
• Return count(upper) - count(lower - 1)

class Solution:
    def countCommas(self, lower: int, upper: int) -> int:
        def count_commas_up_to(n):
            if n < 1000:
                return 0
            
            total = 0
            k = 1
            while 10 ** (3 * k) <= n:
                min_num = 10 ** (3 * k)
                max_num = min(n, 10 ** (3 * k + 3) - 1)
                count = max_num - min_num + 1
                total += k * count
                k += 1
            
            return total
        
        return count_commas_up_to(upper) - count_commas_up_to(lower - 1)

Complexity

• Time: O(log(upper))
• Space: O(1)
• Notes: Optimal solution using mathematical grouping