跳转至

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

题目描述

给你两个正整数 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

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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)
}

方法二

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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)

评论