Count commas in range ii

Math

40.9% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_commas(n: i64) -> i64 {
    // A number with d digits has floor((d-1)/3) commas.
    // We need sum of floor((d_i - 1)/3) for i in 1..=n.
    // Group by number of digits: 1-digit: 1..9, 2-digit: 10..99, etc.
    // For k-digit numbers, commas = (k-1)/3.
    // Count how many k-digit numbers <= n, multiply by (k-1)/3.
    
    if n <= 0 {
      return 0;
    }
    
    let mut result = 0i64;
    let mut lower = 1i64; // start of k-digit numbers
    let mut k = 1u32;
    
    loop {
      let upper = lower * 10 - 1; // end of k-digit numbers
      let commas = ((k - 1) / 3) as i64;
      if lower > n {
        break;
      }
      let count = (n.min(upper) - lower + 1) as i64;
      result += count * commas;
      if upper >= n {
        break;
      }
      lower *= 10;
      k += 1;
    }
    
    result
  }
}