LeetCode 题解工作台
一个区间内所有数乘积的缩写
给你两个正整数 left 和 right ，满足 left 。请你计算 闭区间 [left, right] 中所有整数的 乘积 。 由于乘积可能非常大，你需要将它按照以下步骤 缩写 ： 统计乘积中 后缀 0 的数目，并 移除 这些 0 ，将这个数目记为 C 。 比方说， 1000 中有 3 个后缀 …
1
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数学·driven
答案摘要
class Solution: def abbreviateProduct(self, left: int, right: int) -> str:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
给你两个正整数 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 <= 104
解题思路
方法一
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space depend on the chosen approach: iterative counting and modular arithmetic reduce complexity compared to full multiplication. Logarithmic computation for first digits ensures efficiency for large ranges. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect questions about handling large integer products without overflow.
- question_mark
Look for understanding of separating trailing zeros from significant digits.
- question_mark
Check if the candidate uses math properties like logarithms and modular arithmetic for efficiency.
常见陷阱
外企场景- error
Attempting to multiply all numbers directly, causing overflow.
- error
Ignoring the correct count of trailing zeros leading to wrong exponent.
- error
Incorrectly computing first or last digits without modular or logarithmic methods.
进阶变体
外企场景- arrow_right_alt
Return only the number of trailing zeros for a range product.
- arrow_right_alt
Compute the abbreviated product for non-continuous integer ranges.
- arrow_right_alt
Abbreviate products with different digit limits for the first and last significant digits.