Abbreviating the Product of a Range

Problem

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:

1. Count all trailing zeros in the product and remove them. Let us denote this count as C.
   • For example, there are 3 trailing zeros in 1000, and there are 0 trailing zeros in 546.
2. Denote the remaining number of digits in the product as d. If d > 10, then express the product as <pre>...<suf> where <pre> denotes the first 5 digits of the product, and <suf> denotes the last 5 digits of the product after removing all trailing zeros. If d <= 10, we keep it unchanged.
   • For example, we express 1234567654321 as 12345...54321, but 1234567 is represented as 1234567.
3. Finally, represent the product as a string "<pre>...<suf>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].

Examples

Example 1:

Input: left = 1, right = 4
Output: "24e0"
Explanation: The product is 1 × 2 × 3 × 4 = 24.
There are no trailing zeros, so 24 remains the same. The abbreviation will end with "e0".
Since the number of digits is 2, which is less than 10, we do not have to abbreviate it further.
Thus, the final representation is "24e0".

Example 2:

Input: left = 2, right = 11
Output: "399168e2"
Explanation: The product is 39916800.
There are 2 trailing zeros, which we remove to get 399168. The abbreviation will end with "e2".
The number of digits after removing the trailing zeros is 6, so we do not abbreviate it further.
Hence, the abbreviated product is "399168e2".

Example 3:

Input: left = 371, right = 375
Output: "7219856259e3"
Explanation: The product is 7219856259000.

Constraints:

• 1 <= left <= right <= 10^4

Solution

Method 1 – Math and Simulation

Intuition

The product of a large range can have many trailing zeros and too many digits to store directly. Trailing zeros come from factors of 10 (i.e., pairs of 2 and 5). We can count and remove them as we multiply. To abbreviate, we keep track of the first and last 5 digits (ignoring trailing zeros) using modular arithmetic and floating-point math.

Approach

1. Initialize counters for trailing zeros (cnt), and variables for prefix and suffix.
2. For each number in [left, right]:

• Count and remove factors of 2 and 5, incrementing cnt for each pair.
• Multiply the remaining part into the suffix (modulo 10^10 to avoid overflow).
• Multiply the original number into a floating-point prefix, trimming to 5 digits if it grows too large.

3. After the loop, remove any extra trailing zeros from the suffix.
4. If the number of digits after removing zeros is ≤10, return the number with eC.
5. Otherwise, extract the first 5 and last 5 digits, and format as required.

Code

C++

class Solution {
public:
   string abbreviateProduct(int left, int right) {
      int cnt = 0;
      long long suf = 1;
      double pre = 1.0;
      int mod = 10000000000;
      for (int i = left; i <= right; ++i) {
        int x = i, a = 0, b = 0;
        while (x % 2 == 0) { x /= 2; ++a; }
        while (x % 5 == 0) { x /= 5; ++b; }
        cnt += min(a, b);
        a -= min(a, b);
        b -= min(a, b);
        for (int j = 0; j < a; ++j) suf = (suf * 2) % mod;
        for (int j = 0; j < b; ++j) suf = (suf * 5) % mod;
        suf = (suf * x) % mod;
        pre *= i;
        while (pre >= 1e10) pre /= 10;
      }
      for (int i = 0; i < cnt; ++i) suf /= 10;
      string s = to_string(suf);
      while (s.size() < 10) s = "0" + s;
      int d = 0;
      double t = pre;
      while (t >= 1) { t /= 10; ++d; }
      if (d <= 10) {
        string res = to_string((long long)(pre + 1e-8));
        res.erase(res.find_last_not_of('0') + 1);
        return res + "e" + to_string(cnt);
      }
      string pre_s = to_string((long long)(pre * 1e4 + 1e-8));
      return pre_s.substr(0, 5) + "..." + s.substr(s.size() - 5) + "e" + to_string(cnt);
   }
};

Java

class Solution {
   public String abbreviateProduct(int left, int right) {
      int cnt = 0;
      long suf = 1;
      double pre = 1.0;
      int mod = 1000000000;
      for (int i = left; i <= right; ++i) {
        int x = i, a = 0, b = 0;
        while (x % 2 == 0) { x /= 2; ++a; }
        while (x % 5 == 0) { x /= 5; ++b; }
        int m = Math.min(a, b);
        cnt += m;
        a -= m;
        b -= m;
        for (int j = 0; j < a; ++j) suf = (suf * 2) % mod;
        for (int j = 0; j < b; ++j) suf = (suf * 5) % mod;
        suf = (suf * x) % mod;
        pre *= i;
        while (pre >= 1e10) pre /= 10;
      }
      for (int i = 0; i < cnt; ++i) suf /= 10;
      String s = String.format("%010d", suf);
      int d = 0;
      double t = pre;
      while (t >= 1) { t /= 10; ++d; }
      if (d <= 10) {
        String res = String.valueOf((long)(pre + 1e-8));
        res = res.replaceAll("0+$", "");
        return res + "e" + cnt;
      }
      String pre_s = String.valueOf((long)(pre * 1e4 + 1e-8));
      return pre_s.substring(0, 5) + "..." + s.substring(s.length() - 5) + "e" + cnt;
   }
}

Python

class Solution:
   def abbreviateProduct(self, left: int, right: int) -> str:
      cnt = 0
      suf = 1
      pre = 1.0
      mod = 10 ** 10
      for i in range(left, right + 1):
        x = i
        a = b = 0
        while x % 2 == 0:
           x //= 2
           a += 1
        while x % 5 == 0:
           x //= 5
           b += 1
        m = min(a, b)
        cnt += m
        a -= m
        b -= m
        for _ in range(a):
           suf = (suf * 2) % mod
        for _ in range(b):
           suf = (suf * 5) % mod
        suf = (suf * x) % mod
        pre *= i
        while pre >= 1e10:
           pre /= 10
      for _ in range(cnt):
        suf //= 10
      s = str(suf).zfill(10)
      d = 0
      t = pre
      while t >= 1:
        t /= 10
        d += 1
      if d <= 10:
        res = str(int(pre + 1e-8)).rstrip('0')
        return f"{res}e{cnt}"
      pre_s = str(int(pre * 1e4 + 1e-8))
      return f"{pre_s[:5]}...{s[-5:]}e{cnt}"

Complexity

• ⏰ Time complexity: O(N log N) (for each number, factorization and multiplication)
• 🧺 Space complexity: O(1) (constant extra space)