2117. Abbreviating the Product of a Range (Leetcode Hard)
Abbreviating the Product of a Range - Video Solution
Watch 3 video solutions for Abbreviating the Product of a Range, a hard level problem involving Math. This walkthrough by Programming Live with Larry has 257 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
3trailing zeros in1000, and there are0trailing 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 first5digits of the product, and<suf>denotes the last5digits of the product after removing all trailing zeros. Ifd <= 10, we keep it unchanged.- For example, we express
1234567654321as12345...54321, but1234567is represented as1234567.
- For example, we express
- Finally, represent the product as a string
"<pre>...<suf>eC".- For example,
12345678987600000will 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 = 371, right = 375 Output: "7219856259e3" Explanation: The product is 7219856259000.
Constraints:
1 <= left <= right <= 104
Approach Overview
Problem Overview: Given two integers left and right, compute the product of all numbers in the range [left, right]. The full product grows extremely large, so the output must be abbreviated: keep the first few digits, the last few digits, and represent the number of trailing zeros using scientific-style notation.
Approach 1: Multiplicative Approach with Optimization for Large Numbers (O(n) time, O(1) space)
Iterate through every integer from left to right and maintain a running product. Direct multiplication quickly overflows standard integer ranges, so you track only the significant prefix and suffix. After each multiplication, strip trailing zeros by dividing by 10 and count how many zeros were removed. Keep the last digits using a modulo (commonly 10^10) so the suffix stays bounded, and trim the prefix whenever it grows beyond a safe digit limit. This technique preserves enough information to reconstruct the abbreviated format while avoiding massive integers. Time complexity is O(n) because you process each number once, and space complexity is O(1). The logic relies heavily on careful numeric manipulation, making it a good exercise in math and large-number handling.
Approach 2: Logarithmic Reduction to Avoid Overflow (O(n) time, O(1) space)
Instead of maintaining the full prefix directly, compute the leading digits using logarithms. The key observation: log10(a × b) = log10(a) + log10(b). Sum log10(i) for every i in the range to estimate the magnitude of the product. The fractional part of this log value determines the leading digits via exponentiation. In parallel, track the suffix digits using modular multiplication while removing trailing zeros the same way as in the previous approach. This separates the concerns: logs estimate the prefix, while modular arithmetic maintains the suffix. Time complexity remains O(n) and space complexity O(1). This approach is common in problems involving extremely large numbers and scientific notation, often appearing in math or number theory contexts.
Recommended for interviews: The multiplicative trimming approach is usually preferred. It demonstrates that you understand how to control integer growth, remove trailing zeros, and keep both prefix and suffix digits without overflow. The logarithmic method shows deeper numerical insight and is useful when the prefix must be derived analytically rather than maintained directly.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Multiplicative Approach with Prefix/Suffix Trimming | O(n) | O(1) | General solution when you want direct control over trailing zeros and digit trimming during multiplication. |
| Logarithmic Reduction with Modular Suffix Tracking | O(n) | O(1) | Useful when the leading digits are easier to derive from logarithmic magnitude rather than storing large prefixes. |