Abbreviating the product of a range

Math Number Theory

24.9% acceptance

Feb 25, 2026

162

You are given two positive integers left and right with left <= right. Calculate the product of all integers in the inclusive range [left, right]. Since the product may be very large, you will abbreviate it following these steps: Count all trailing zeros in the product and remove them. Let us denote this count as C. Denote the remaining number of digits in the product as d. If d > 10, then express the product as

... where  denotes the first 5 digits of the product, and  denotes the last 5 digits of the product after removing all trailing zeros. If d <= 10, we keep it unchanged.
Finally, represent the product as a string "...eC".
For example, 12345678987600000 will be represented as "12345...89876e5".
Return a string denoting the abbreviated product of all integers in the inclusive range [left, right].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn abbreviate_product(left: i32, right: i32) -> String {
    let tail_mod: u64 = 10_000_000_000_000; // 10^13
    let mut c2: u64 = 0;
    let mut c5: u64 = 0;
    let mut log_sum: f64 = 0.0;
    let mut tail: u64 = 1;
    let mut head: f64 = 1.0; // tracks prefix digits, normalized to avoid overflow

    for x in left..=right {
      log_sum += (x as f64).log10();
      let mut x = x as u64;
      while x % 2 == 0 {
        c2 += 1;
        x /= 2;
      }
      while x % 5 == 0 {
        c5 += 1;
        x /= 5;
      }
      tail = (tail as u128 * x as u128 % tail_mod as u128) as u64;
      head *= x as f64;
      while head >= 1e15 {
        head /= 10.0;
      }
    }

    let c = c2.min(c5);

    // Multiply excess 2s and 5s back into tail and head
    tail = (tail as u128 * Self::pow_mod(2, c2 - c, tail_mod) as u128 % tail_mod as u128) as u64;
    tail = (tail as u128 * Self::pow_mod(5, c5 - c, tail_mod) as u128 % tail_mod as u128) as u64;
    for _ in 0..(c2 - c) {
      head *= 2.0;
      while head >= 1e15 { head /= 10.0; }
    }
    for _ in 0..(c5 - c) {
      head *= 5.0;
      while head >= 1e15 { head /= 10.0; }
    }

    let log_sig = log_sum - c as f64; // log10 of significant product
    let d = log_sig as usize + 1; // number of significant digits

    if d <= 10 {
      return format!("{}e{}", tail, c);
    }

    // Abbreviated: first 5 and last 5 digits
    let suf = format!("{:05}", tail % 100_000);
    // Normalize head to exactly 5 digits for the prefix
    while head >= 100_000.0 { head /= 10.0; }
    while head < 10_000.0 { head *= 10.0; }
    let pre = format!("{:05}", head as u64);

    format!("{}...{}e{}", pre, suf, c)
  }

  fn pow_mod(mut base: u64, mut exp: u64, m: u64) -> u64 {
    let mut result = 1u64;
    base %= m;
    while exp > 0 {
      if exp & 1 == 1 {
        result = (result as u128 * base as u128 % m as u128) as u64;
      }
      exp >>= 1;
      base = (base as u128 * base as u128 % m as u128) as u64;
    }
    result
  }
}