Question

2117. 一个区间内所有数乘积的缩写

English Version

题目描述

给你两个正整数 left 和 right ，满足 left <= right 。请你计算 闭区间 [left, right] 中所有整数的 乘积 。

由于乘积可能非常大，你需要将它按照以下步骤 缩写 ：

1. 统计乘积中 后缀 0 的数目，并 移除 这些 0 ，将这个数目记为 C 。
   • 比方说，1000 中有 3 个后缀 0 ，546 中没有后缀 0 。
2. 将乘积中剩余数字的位数记为 d 。如果 d > 10 ，那么将乘积表示为 <pre>...<suf> 的形式，其中 <pre> 表示乘积最 开始 的 5 个数位，<suf> 表示删除后缀 0 之后 结尾的 5 个数位。如果 d <= 10 ，我们不对它做修改。
   • 比方说，我们将 1234567654321 表示为 12345...54321 ，但是 1234567 仍然表示为 1234567 。
3. 最后，将乘积表示为 字符串 "<pre>...<suf>eC" 。
   • 比方说，12345678987600000 被表示为 "12345...89876e5" 。

请你返回一个字符串，表示 闭区间 [left, right] 中所有整数 乘积 的 缩写 。

 

示例 1：

输入：left = 1, right = 4
输出："24e0"
解释：
乘积为 1 × 2 × 3 × 4 = 24 。
由于没有后缀 0 ，所以 24 保持不变，缩写的结尾为 "e0" 。
因为乘积的结果是 2 位数，小于 10 ，所欲我们不进一步将它缩写。
所以，最终将乘积表示为 "24e0" 。

示例 2：

输入：left = 2, right = 11
输出："399168e2"
解释：乘积为 39916800 。
有 2 个后缀 0 ，删除后得到 399168 。缩写的结尾为 "e2" 。 
删除后缀 0 后是 6 位数，不需要进一步缩写。 
所以，最终将乘积表示为 "399168e2" 。

示例 3：

输入：left = 371, right = 375
输出："7219856259e3"
解释：乘积为 7219856259000 。

 

提示：

• 1 <= left <= right <= 104

解法

方法一

import numpy


class Solution:
  def abbreviateProduct(self, left: int, right: int) -> str:
    cnt2 = cnt5 = 0
    z = numpy.float128(0)
    for x in range(left, right + 1):
      z += numpy.log10(x)
      while x % 2 == 0:
        x //= 2
        cnt2 += 1
      while x % 5 == 0:
        x //= 5
        cnt5 += 1
    c = cnt2 = cnt5 = min(cnt2, cnt5)
    suf = y = 1
    gt = False
    for x in range(left, right + 1):
      while cnt2 and x % 2 == 0:
        x //= 2
        cnt2 -= 1
      while cnt5 and x % 5 == 0:
        x //= 5
        cnt5 -= 1
      suf = suf * x % 100000
      if not gt:
        y *= x
        gt = y >= 1e10
    if not gt:
      return str(y) + "e" + str(c)
    pre = int(pow(10, z - int(z) + 4))
    return str(pre) + "..." + str(suf).zfill(5) + "e" + str(c)

class Solution {

  public String abbreviateProduct(int left, int right) {
    int cnt2 = 0, cnt5 = 0;
    for (int i = left; i <= right; ++i) {
      int x = i;
      for (; x % 2 == 0; x /= 2) {
        ++cnt2;
      }
      for (; x % 5 == 0; x /= 5) {
        ++cnt5;
      }
    }
    int c = Math.min(cnt2, cnt5);
    cnt2 = cnt5 = c;
    long suf = 1;
    double pre = 1;
    boolean gt = false;
    for (int i = left; i <= right; ++i) {
      for (suf *= i; cnt2 > 0 && suf % 2 == 0; suf /= 2) {
        --cnt2;
      }
      for (; cnt5 > 0 && suf % 5 == 0; suf /= 5) {
        --cnt5;
      }
      if (suf >= (long) 1e10) {
        gt = true;
        suf %= (long) 1e10;
      }
      for (pre *= i; pre > 1e5; pre /= 10) {
      }
    }
    if (gt) {
      return (int) pre + "..." + String.format("%05d", suf % (int) 1e5) + "e" + c;
    }
    return suf + "e" + c;
  }
}

class Solution {
public:
  string abbreviateProduct(int left, int right) {
    int cnt2 = 0, cnt5 = 0;
    for (int i = left; i <= right; ++i) {
      int x = i;
      for (; x % 2 == 0; x /= 2) {
        ++cnt2;
      }
      for (; x % 5 == 0; x /= 5) {
        ++cnt5;
      }
    }
    int c = min(cnt2, cnt5);
    cnt2 = cnt5 = c;
    long long suf = 1;
    long double pre = 1;
    bool gt = false;
    for (int i = left; i <= right; ++i) {
      for (suf *= i; cnt2 && suf % 2 == 0; suf /= 2) {
        --cnt2;
      }
      for (; cnt5 && suf % 5 == 0; suf /= 5) {
        --cnt5;
      }
      if (suf >= 1e10) {
        gt = true;
        suf %= (long long) 1e10;
      }
      for (pre *= i; pre > 1e5; pre /= 10) {
      }
    }
    if (gt) {
      char buf[10];
      snprintf(buf, sizeof(buf), "%0*lld", 5, suf % (int) 1e5);
      return to_string((int) pre) + "..." + string(buf) + "e" + to_string(c);
    }
    return to_string(suf) + "e" + to_string(c);
  }
};

func abbreviateProduct(left int, right int) string {
  cnt2, cnt5 := 0, 0
  for i := left; i <= right; i++ {
    x := i
    for x%2 == 0 {
      cnt2++
      x /= 2
    }
    for x%5 == 0 {
      cnt5++
      x /= 5
    }
  }
  c := int(math.Min(float64(cnt2), float64(cnt5)))
  cnt2 = c
  cnt5 = c
  suf := int64(1)
  pre := float64(1)
  gt := false
  for i := left; i <= right; i++ {
    for suf *= int64(i); cnt2 > 0 && suf%2 == 0; {
      cnt2--
      suf /= int64(2)
    }
    for cnt5 > 0 && suf%5 == 0 {
      cnt5--
      suf /= int64(5)
    }
    if float64(suf) >= 1e10 {
      gt = true
      suf %= int64(1e10)
    }
    for pre *= float64(i); pre > 1e5; {
      pre /= 10
    }
  }
  if gt {
    return fmt.Sprintf("%05d...%05de%d", int(pre), int(suf)%int(1e5), c)
  }
  return fmt.Sprintf("%de%d", suf, c)
}

方法二

class Solution:
  def abbreviateProduct(self, left: int, right: int) -> str:
    cnt2 = cnt5 = 0
    for x in range(left, right + 1):
      while x % 2 == 0:
        cnt2 += 1
        x //= 2
      while x % 5 == 0:
        cnt5 += 1
        x //= 5
    c = cnt2 = cnt5 = min(cnt2, cnt5)
    pre = suf = 1
    gt = False
    for x in range(left, right + 1):
      suf *= x
      while cnt2 and suf % 2 == 0:
        suf //= 2
        cnt2 -= 1
      while cnt5 and suf % 5 == 0:
        suf //= 5
        cnt5 -= 1
      if suf >= 1e10:
        gt = True
        suf %= int(1e10)
      pre *= x
      while pre > 1e5:
        pre /= 10
    if gt:
      return str(int(pre)) + "..." + str(suf % int(1e5)).zfill(5) + 'e' + str(c)
    return str(suf) + "e" + str(c)