Description#
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.<ul>
<li>For example, there are <code>3</code> trailing zeros in <code>1000</code>, and there are <code>0</code> trailing zeros in <code>546</code>.</li>
</ul>
</li>
<li>Denote the remaining number of digits in the product as <code>d</code>. If <code>d > 10</code>, then express the product as <code><pre>...<suf></code> where <code><pre></code> denotes the <strong>first</strong> <code>5</code> digits of the product, and <code><suf></code> denotes the <strong>last</strong> <code>5</code> digits of the product <strong>after</strong> removing all trailing zeros. If <code>d <= 10</code>, we keep it unchanged.
<ul>
<li>For example, we express <code>1234567654321</code> as <code>12345...54321</code>, but <code>1234567</code> is represented as <code>1234567</code>.</li>
</ul>
</li>
<li>Finally, represent the product as a <strong>string</strong> <code>"<pre>...<suf>eC"</code>.
<ul>
<li>For example, <code>12345678987600000</code> will be represented as <code>"12345...89876e5"</code>.</li>
</ul>
</li>
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 = 371, right = 375
Output: "7219856259e3"
Explanation: The product is 7219856259000.
Constraints:
1 <= left <= right <= 104
Solutions#
Solution 1#
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)
}
|
Solution 2#
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)
|
