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

难度: Hard

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

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

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

Submission

运行时间: 435 ms

内存: 16.0 MB

class Solution:
    def abbreviateProduct(self, left: int, right: int) -> str:
        M = 10 ** 10
        MOD = 10 ** 16
        zero = 0   
        # 计算后缀，并统计末位 0 的个数
        suf = 1
        for i in range(left, right + 1):
            suf *= i
            while suf % 10 == 0:
                zero += 1
                suf //= 10
            
            suf %= MOD

        if suf < M: return str(suf) + 'e' + str(zero)   
        
        # 计算前缀
        pref = 1
        for i in range(left, right + 1):
            pref *= i
            while pref >= MOD:
                pref //= 10 

        return str(pref)[:5] + '...' + str(suf)[-5:] + 'e' + str(zero)

Explain

本题解思路主要分为两部分：首先，计算区间 [left, right] 内所有整数的乘积，并移除乘积中的所有后缀0，同时计算这些0的数量。其次，根据乘积的大小来决定如何缩写这个数字。如果乘积的有效位数（不含后缀0）超过10位，则只显示前5位和后5位，并用省略号连接；如果不超过10位，则直接显示。最终输出字符串格式为 '<pre>...<suf>eC'。为了防止在乘积计算过程中发生溢出，使用了模运算来保持数字在可控范围内。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def abbreviateProduct(self, left: int, right: int) -> str:
        M = 10 ** 10  # 定义一个大数 M 用于比较大小
        MOD = 10 ** 16  # 定义一个 MOD 用于取模，保证数字不会过大
        zero = 0  # 后缀0的数量
        suf = 1  # 用于计算乘积，并去除后缀0
        for i in range(left, right + 1):
            suf *= i
            while suf % 10 == 0:  # 移除后缀的0
                zero += 1
                suf //= 10
            suf %= MOD  # 防止溢出
        if suf < M: return str(suf) + 'e' + str(zero)  # 如果位数不超过10位，直接返回
        pref = 1  # 计算前缀
        for i in range(left, right + 1):
            pref *= i
            while pref >= MOD:  # 控制前缀的大小
                pref //= 10
        return str(pref)[:5] + '...' + str(suf)[-5:] + 'e' + str(zero)  # 返回缩写形式

Explore

在该题解中，选择两次遍历的原因在于需求的不同部分对数值精度的要求不同。第一次遍历用于计算并缩减后缀的数字，同时去除所有后缀的0并保持数值在一个较小的范围内（使用MOD进行取模）。这是为了精确地计算出后缀的5位数字和0的数量。第二次遍历则是为了获取足够大的前缀数字，尽可能保持高位的信息以便于截取前5位。虽然理论上可以在一次遍历中同时更新前缀和后缀，但这样做可能需要在每一步都进行复杂的判断和调整，以保持数字大小适中并同时保留必要的高位和低位信息，这可能会增加算法的复杂性和执行时间。因此，采用两次遍历的方法可以更清晰地分别处理并优化这两部分的精度和性能。

在移除乘积中的后缀0时，每当乘积可以被10整除，即末尾为0时，通过除以10来移除这个0，并记录0的数量。这种方法确保了每次操作都是精确的，因为整数除法在这里是精确的操作，不会引入任何浮点数运算的误差。去除0的操作只影响数值的尾部，不会改变其它位的值，因此不会在去除大量0后使结果的低位出现错误。只要正确记录了0的数量，并保持其它位的正确计算，就能确保整体计算的精度。

在这种情况下，MOD的大小选择为10^16主要是基于两个考虑：一是确保在计算过程中的数字大小可控，避免因整数溢出导致计算错误；二是保证足够的数字精度来获取必要的前5位和后5位。选择10^16是因为它足够大，可以在绝大多数情况下保持计算的精确性，同时又不至于过大导致处理速度过慢。如果MOD设置得太小，可能无法保留足够的数字位数，导致计算结果不精确；设置得太大，则可能导致数字处理过程中的性能问题。因此，10^16是一个在保证性能和精度之间权衡的合适选择。不过，确实存在极端情况下可能因MOD选取不当导致计算错误，这需要根据具体问题的数据范围和需求来调整MOD的大小。