You are given two positive integers left
and right
with left <= right
. Calculate the product of all integers in the inclusive range [left, right]
.
Since the product may be very large, you will abbreviate it following these steps:
- Count all trailing zeros in the product and remove them. Let us denote this count as
C
.- For example, there are
3
trailing zeros in1000
, and there are0
trailing zeros in546
.
- For example, there are
- Denote the remaining number of digits in the product as
d
. Ifd > 10
, then express the product as<pre>...<suf>
where<pre>
denotes the first5
digits of the product, and<suf>
denotes the last5
digits of the product after removing all trailing zeros. Ifd <= 10
, we keep it unchanged.- For example, we express
1234567654321
as12345...54321
, but1234567
is represented as1234567
.
- For example, we express
- Finally, represent the product as a string
"<pre>...<suf>eC"
.- For example,
12345678987600000
will be represented as"12345...89876e5"
.
- For example,
Return a string denoting the abbreviated product of all integers in the inclusive range [left, right]
.
Example 1:
Input: left = 1, right = 4 Output: "24e0" Explanation: The product is 1 × 2 × 3 × 4 = 24. There are no trailing zeros, so 24 remains the same. The abbreviation will end with "e0". Since the number of digits is 2, which is less than 10, we do not have to abbreviate it further. Thus, the final representation is "24e0".
Example 2:
Input: left = 2, right = 11 Output: "399168e2" Explanation: The product is 39916800. There are 2 trailing zeros, which we remove to get 399168. The abbreviation will end with "e2". The number of digits after removing the trailing zeros is 6, so we do not abbreviate it further. Hence, the abbreviated product is "399168e2".
Example 3:
Input: left = 999998, right = 1000000 Output: "99999...00002e6" Explanation: The above diagram shows how we abbreviate the product to "99999...00002e6". - It has 6 trailing zeros. The abbreviation will end with "e6". - The first 5 digits are 99999. - The last 5 digits after removing trailing zeros is 00002.
Constraints:
1 <= left <= right <= 106
Solution: Prefix + Suffix
Since we only need the first 5 digits and last 5 digits, we can compute prefix and suffix separately with 15+ effective digits. Note, if using long/int64 with (18 – 6) = 12 effective digits, it may fail on certain test cases. Thus, here we use Python with 18 effective digits.
Time complexity: O(mlog(right)) where m = right – left + 1
Space complexity: O(1)
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Author: Huahua class Solution: def abbreviateProduct(self, left: int, right: int) -> str: kMax = 10 ** 18 prefix = 1 suffix = 1 c = 0 for i in range(left, right + 1): prefix *= i while prefix >= kMax: prefix //= 10 suffix *= i while suffix % 10 == 0: suffix //= 10 c += 1 suffix %= kMax p, s = str(prefix), str(suffix) return (s if len(s) <= 10 else p[:5] + "..." + s[-5:]) + "e" + str(c); |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment