Hard

题目描述

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

由于乘积可能非常大，你需要按照以下步骤对其进行缩写：

  1. 计算乘积中所有尾随零的数量并移除它们。将此数量记为 C。

    • 例如，1000 有 3 个尾随零，546 有 0 个尾随零。

  2. 设移除所有尾随零后剩余的位数为 d。如果 d > 10，则将乘积表示为 <pre>...<suf>，其中 <pre> 表示乘积的前 5 位数字，<suf> 表示移除所有尾随零后的后 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。
没有尾随零，所以 24 保持不变。缩写将以 "e0" 结尾。
由于位数是 2，小于 10，我们不需要进一步缩写。
因此，最终表示是 "24e0"。

示例 2：

输入：left = 2, right = 11
输出："399168e2"
解释：乘积是 39916800。
有 2 个尾随零，移除后得到 399168。缩写将以 "e2" 结尾。
移除尾随零后的位数是 6，所以我们不进一步缩写。
因此，缩写乘积是 "399168e2"。

示例 3：

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

约束：

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

解题思路

这是一道需要处理大数运算和数学技巧的困难题目。我们需要分别计算三个部分：尾随零的数量、后五位数字和前五位数字。

核心思路：

  1. 计算尾随零数量 C：

    • 尾随零由因子 2 和 5 的配对产生，数量等于 min(因子2的个数, 因子5的个数)
    • 通常因子 2 比因子 5 多，所以只需计算因子 5 的个数

  2. 计算后五位数字：

    • 在计算乘积时，同时移除配对的因子 2 和 5（避免产生尾随零）
    • 对剩余部分取模 10^5 得到后五位

  3. 计算前五位数字：

    • 使用对数性质：log₁₀(a×b) = log₁₀(a) + log₁₀(b)
    • 计算 sum = Σlog₁₀(i) for i in [left, right]
    • 设 sum = integer_part + fractional_part
    • 前五位 = floor(10^(fractional_part + 4))

  4. 格式化输出：

    • 如果移除尾随零后位数 ≤ 10，直接输出完整数字
    • 否则输出 “前五位…后五位eC” 格式

这种方法避免了直接计算可能溢出的大数乘积，而是巧妙地分别处理各个组成部分。

代码实现

class Solution {
public:
    string abbreviateProduct(int left, int right) {
        // 计算因子5的数量（尾随零数量）
        int trailingZeros = 0;
        for (int i = left; i <= right; i++) {
            int num = i;
            while (num % 5 == 0) {
                trailingZeros++;
                num /= 5;
            }
        }
        
        // 计算后五位数字（移除配对的2和5）
        long long suffix = 1;
        int removed2 = 0, removed5 = 0;
        const long long MOD = 100000;
        
        for (int i = left; i <= right; i++) {
            long long num = i;
            
            // 移除因子5
            while (num % 5 == 0 && removed5 < trailingZeros) {
                num /= 5;
                removed5++;
            }
            
            // 移除因子2
            while (num % 2 == 0 && removed2 < trailingZeros) {
                num /= 2;
                removed2++;
            }
            
            suffix = (suffix * num) % MOD;
        }
        
        // 计算总位数
        double logSum = 0;
        for (int i = left; i <= right; i++) {
            logSum += log10(i);
        }
        int totalDigits = (int)logSum + 1 - trailingZeros;
        
        if (totalDigits <= 10) {
            return to_string(suffix) + "e" + to_string(trailingZeros);
        }
        
        // 计算前五位数字
        double fractionalPart = logSum - floor(logSum);
        long long prefix = (long long)pow(10, fractionalPart + 4);
        
        return to_string(prefix) + "..." + string(5 - to_string(suffix).length(), '0') + to_string(suffix) + "e" + to_string(trailingZeros);
    }
};

class Solution:
    def abbreviateProduct(self, left: int, right: int) -> str:
        import math
        
        # 计算因子5的数量（尾随零数量）
        trailing_zeros = 0
        for i in range(left, right + 1):
            num = i
            while num % 5 == 0:
                trailing_zeros += 1
                num //= 5
        
        # 计算后五位数字（移除配对的2和5）
        suffix = 1
        removed_2 = removed_5 = 0
        MOD = 100000
        
        for i in range(left, right + 1):
            num = i
            
            # 移除因子5
            while num % 5 == 0 and removed_5 < trailing_zeros:
                num //= 5
                removed_5 += 1
            
            # 移除因子2
            while num % 2 == 0 and removed_2 < trailing_zeros:
                num //= 2
                removed_2 += 1
            
            suffix = (suffix * num) % MOD
        
        # 计算总位数
        log_sum = sum(math.log10(i) for i in range(left, right + 1))
        total_digits = int(log_sum) + 1 - trailing_zeros
        
        if total_digits <= 10:
            return str(suffix) + "e" + str(trailing_zeros)
        
        # 计算前五位数字
        fractional_part = log_sum - math.floor(log_sum)
        prefix = int(10 ** (fractional_part + 4))
        
        suffix_str = f"{suffix:05d}"
        return f"{prefix}...{suffix_str}e{trailing_zeros}"

public class Solution {
    public string AbbreviateProduct(int left, int right) {
        // 计算因子5的数量（尾随零数量）
        int trailingZeros = 0;
        for (int i = left; i <= right; i++) {
            int num = i;
            while (num % 5 == 0) {
                trailingZeros++;
                num /= 5;
            }
        }
        
        // 计算后五位数字（移除配对的2和5）
        long suffix = 1;
        int removed2 = 0, removed5 = 0;
        const long MOD = 100000;
        
        for (int i = left; i <= right; i++) {
            long num = i;
            
            // 移除因子5
            while (num % 5 == 0 && removed5 < trailingZeros) {
                num /= 5;
                removed5++;
            }
            
            // 移除因子2
            while (num % 2 == 0 && removed2 < trailingZeros) {
                num /= 2;
                removed2++;
            }
            
            suffix = (suffix * num) % MOD;
        }
        
        // 计算总位数
        double logSum = 0;
        for (int i = left; i <= right; i++) {
            logSum += Math.Log10(i);
        }
        int totalDigits = (int)logSum + 1 - trailingZeros;
        
        if (totalDigits <= 10) {
            return suffix + "e" + trailingZeros;
        }
        
        // 计算前五位数字
        double fractionalPart = logSum - Math.Floor(logSum);
        long prefix = (long)Math.Pow(10, fractionalPart + 4);
        
        string suffixStr = suffix.ToString("D5");
        return $"{prefix}...{suffixStr}e{trailingZeros}";
    }
}

var abbreviateProduct = function(left, right) {
    let twos = 0, fives = 0;
    let logSum = 0;
    
    // Count factors of 2 and 5, and calculate log sum
    for (let i = left; i <= right; i++) {
        let num = i;
        while (num % 2 === 0) {
            twos++;
            num /= 2;
        }
        num = i;
        while (num % 5 === 0) {
            fives++;
            num /= 5;
        }
        logSum += Math.log10(i);
    }
    
    let trailingZeros = Math.min(twos, fives);
    twos -= trailingZeros;
    fives -= trailingZeros;
    
    // Calculate remaining digits
    let remainingDigits = Math.floor(logSum) + 1;
    
    if (remainingDigits <= 10) {
        // Calculate exact product without trailing zeros
        let product = 1n;
        for (let i = left; i <= right; i++) {
            product *= BigInt(i);
        }
        
        // Remove trailing zeros
        while (product % 10n === 0n) {
            product /= 10n;
        }
        
        return product.toString() + "e" + trailingZeros;
    } else {
        // Need to abbreviate
        // Calculate first 5 digits using logarithms
        let fractionalPart = logSum - Math.floor(logSum);
        let first5 = Math.floor(Math.pow(10, fractionalPart + 4));
        
        // Calculate last 5 digits using modular arithmetic
        let last5 = 1;
        const MOD = 100000;
        
        for (let i = left; i <= right; i++) {
            last5 = (last5 * i) % MOD;
        }
        
        // Remove factors of 2 and 5 from last5
        for (let i = 0; i < twos; i++) {
            last5 = (last5 * 2) % MOD;
        }
        for (let i = 0; i < fives; i++) {
            last5 = (last5 * 5) % MOD;
        }
        
        // Format last5 to 5 digits
        let last5Str = last5.toString().padStart(5, '0');
        
        return first5 + "..." + last5Str + "e" + trailingZeros;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
总体O(n log n)O(1)

详细分析：

  • 时间复杂度：O(n log n)，其中 n = right - left + 1
    • 计算因子5的数量：O(n log n)，每个数字最多除以5约log₅(n)次
    • 计算后五位：O(n log n)，每个数字最多除以2和5各约log(n)次
    • 计算对数和：O(n)
    • 其他操作：O(1)
  • 空间复杂度：O(1)，只使用常数级别的额外空间

相关题目