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

2021/12/30 6:09:40

本文主要是介绍LeetCode 2117. 一个区间内所有数乘积的缩写 数学,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

题目描述

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

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

  • 统计乘积中 后缀 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] 中所有整数 乘积缩写

样例

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


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

productdrawio.png

输入:left = 999998, right = 1000000
输出:"99999...00002e6"
解释:
上图展示了如何得到乘积的缩写 "99999...00002e6"。
- 总共有 6 个后缀 0。缩写的结尾为 "e6"。
- 开头 5 个数位是 99999。
- 删除后缀 0 后结尾 5 个数字为 00002。


输入:left = 256, right = 65535
输出:"23510...78528e16317"
解释:
乘积是一个非常大的数字:
- 总共有 16317 个后缀 0。缩写结尾为 "e16317"。
- 开头 5 个数字为 23510。
- 删除后缀 0 后,结尾 5 个数字为 78528。
所以,乘积的缩写为 "23510...78528e16317"。

限制

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

算法

(数学) \(O(n)\)

本题要求的分为三部分,第一部分求后缀 0 的个数,第二部分求低 5 位,第三部分求高 5 位。

  1. 第一部分:一个数末尾0的个数\(min(cnt_5, cnt_2)\),对于阶乘的质因子个数,有勒让德定理:

    在正数 \(n !\) 的素因子标准分解式中, 素数 \(p\) 的指数记作 \(L_{p}(n !)\) , 则 \(L_{p}(n !)=\sum_{k \geq 1}\left[\frac{n}{p^{k}}\right]\).

    img

    即\(right\) 阶乘中因数 \(5\) 的个数减去 \(left - 1\) 阶乘中因数 \(5\) 的个数,与 \(right\) 阶乘中因数 \(2\) 的个数减去 \(left - 1\) 阶乘中因数 \(2\) 的个数取最小值后,就是区间后缀 0 的个数 \(C\)。

  2. 第二部分:从 \(left\) 累乘到 \(right\),过程中,对乘数总共进行 \(C\)次扣除因数 \(2\) 和因数 \(5\),并对结果进行 \(100000\) 取余。

  3. 第三部分:

    • 设 \(P=a_{1} a_{2} a_{3} \ldots a_{n}\) ,则\(\lg P=\lg a_{1}+\lg a_{2}+\lg a_{3}+\cdots+\lg a_{n}\) 。

    • 即\(P\)的位数\(S=\lg P\) ,则 \(P=10^{S}\) 。此时将 \(S\) 分为整数部分\(S_{1}\) 和小数部分 \(S_{2}\) ,则 \(P=10^{S_{1}} \cdot 10^{S_{2}}\) 。\(10^{S_{1}}\)代表后面的0个数,\(P\)真正有效非后缀0的是\(10^{S_{2}}\)。

    • \(P\) 的高五位就是 \(P\) 不断除以 10 直到最终只剩下五位,此时高五位相当于 \(10^{S_{2}+4}= 10^{S - floor(s) + 4}\) 。

  4. 求解第三部分过程中,如果发现 \(S_1 < 10 + C\),则说明 \(d\) 小于等于 10 位,此时可以暴力求解第二部分的结果。

时间复杂度

  • 求解第一部分的时间复杂度为 \(O(log n)\)。
  • 求解第二部分的时间复杂度为 \(O(n)\)。
  • 求解第三部分的时间复杂度也为 \(O(n)\)。
  • 故总时间复杂度为 \(O(n)\)。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
private:
    int calc(int x, int p) {
        int res = 0;
        while (x) {
            res += x / p;
            x /= p;
        }

        return res;
    }

    string brute_force(int zero, int left, int right) {
        LL res = 1;
        int cnt2 = zero, cnt5 = zero;
        for (int i = left; i <= right; i++) {
            int x = i;
            while (x % 2 == 0 && cnt2 > 0) {
                x /= 2;
                cnt2--;
            }

            while (x % 5 == 0 && cnt5 > 0) {
                x /= 5;
                cnt5--;
            }

            res *= x;
        }

        char ans[30];
        sprintf(ans, "%llde%d", res, zero);
        return ans;
    }

public:
    string abbreviateProduct(int left, int right) {
        int zero = min(calc(right, 5) - calc(left - 1, 5),
            calc(right, 2) - calc(left - 1, 2));

        int low = 1;
        int cnt2 = zero, cnt5 = zero;
        for (int i = left; i <= right; i++) {
            int x = i;
            while (x % 2 == 0 && cnt2 > 0) {
                x /= 2;
                cnt2--;
            }

            while (x % 5 == 0 && cnt5 > 0) {
                x /= 5;
                cnt5--;
            }

            low = (LL)(low) * x % 100000;
        }

        long double s = 0;
        for (int i = left; i <= right; i++)
            s += log10(i);

        if (s <= 10 + zero)
            return brute_force(zero, left, right);

        int high = pow(10, s - floor(s) + 4);

        char ans[30];
        sprintf(ans, "%d...%05de%d", high, low, zero);
        return ans;
    }
};


这篇关于LeetCode 2117. 一个区间内所有数乘积的缩写 数学的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程