Count Commas in Range - Solution & Explanation

Problem Overview: Given two integers low and high, count how many comma separators appear if every number in that inclusive range is written using standard thousands formatting (e.g., 1,000, 1,000,000). Each number contributes floor((digits-1)/3) commas based on its digit length.

Approach 1: Brute Force Formatting (O(n log n) time, O(1) space)

Iterate through every integer from low to high. For each number, compute its digit length using log10 or string conversion. The number of commas contributed by that value equals (digits - 1) / 3 using integer division. Accumulate this value across the entire range. This approach is easy to reason about but becomes slow when the range is large because you process every number individually.

Approach 2: Digit Range Counting / Brain Teaser (O(log n) time, O(1) space)

Instead of iterating through each value, group numbers by digit length. All numbers with the same digit length produce the same number of commas. For example, numbers with 4–6 digits each contain one comma, while numbers with 7–9 digits contain two. Compute how many numbers of each digit length fall within [low, high], then multiply by floor((digits-1)/3). This converts the problem into counting intervals like [1000, 999999] intersected with the query range.

This method works because comma placement depends only on digit length, not the specific number. The number of digit groups is small (at most around 12–18 for typical constraints), so you only iterate through digit boundaries rather than the full range. The technique relies on simple arithmetic and is a common pattern in math and counting problems where ranges can be aggregated instead of enumerated.

Recommended for interviews: The digit-range math approach. Brute force shows the correct observation about how commas relate to digit length, but the optimized solution demonstrates stronger math reasoning and range counting skills. Interviewers typically expect the O(log n) grouping method once you recognize that comma count depends only on the number of digits.