Python 3: TC O((right-left)*log(right)) SC O(1): Tricks for First and Last Five Digits
Intuition\n\nThe easy case is when the explicit product is less than a few thousand digits, in which case we can use Python\'s arbitrary precision math. Unfortu
# Intuition\n\nThe easy case is when the explicit product is less than a few thousand digits, in which case we can use Python\'s arbitrary precision math. Unfortunately there\'s a limit of 4300 digits and we can easily hit that because we\'re basically computing factorials.\n\n## Counting Trailing Zeros\n\nIf there\'s a trailing zero then the product is divisible by `10 == 2*5`.\n\nThat means if we have `twos` factors of `2` and `fives` factors of `5` then we will have `min(twos, fives)` tailing zeros.\n\n## Last Five Digits\n\nThe last five is a bit easier to get. We know that the resulting number is something like this:\n```a\n................ ABCDE 0000000..00000\n---------------- ----- --------------\nfirst D-1 digits  last     C trailing zeros\n                  five\n```\n\nThe whole product is `left * ... * right = 2**twos * 5**fives * rest` where `rest` are all prime factors that are not `2` or `5`.\n\nThe trailing zeros account for `2**C * 5**C`.\n\nTherefore we need the last five digits of `rest * 2**(twos-C) * 5**(fives-C)`.\n\nTo get this is easier than it might look:\n* we can get the last five digits of `rest` by brute-force\n  * for each `x` divide out the `2` and `5` factors\n  * then include `x` in the product and take the residue mod `1e5`\n* then we have `twos-C` factors of two, multiply those in and take the residue each time\n* and we have `fives-C` factors of five, same thing\n\nEither `twos-C` or `fives-C` will be zero so we won\'t get any additional trailing zeros.\n\nWe only need the last five digits of `rest` becauase we know the last five digits of `lhs * rhs` only depend on the last five digits of both. And we know none of them will be zero because we divided out all the factors that can possibly give us zero.\n\n## First Five Digits\n\nThe insight we need here is that if we get `log10(product)` then it can be written as\n\n```a\nlog10(first * 10**(digits-1) + second * 10**(digits-2) + ...)`\n = log10(10**(digits-1)) + log10(first + second/10 + ... + fifth/1e4)\n   ---------------------   ------------------------------------------\n      integer                   < 10: decimal\n```\n\nSo if we get the `log10` of the product (floating point), then the decimal part gives us the digits. We only need the first five so if we\'re careful with floating-point math we can extract them from the log10.\n\n**Tricky part:** if we add up the log10 of each `x` in `left..right` then we lose some precision because the sum can be order `1e4` (see Stirling\'s approximation). This means we\'ll lose about four digits of precision when adding log10s, e.g. `4000.<lhs_digits> + 0.<rhs_digits>` will drop some digits of precision from `rhs_digits`. **We need all the digits we can get to maximum precision or else we\'ll get off-by-one errors.**\n\nTo avoid this we do the following:\n* for each `x`, divide out the factors of 10\n* **then** take the log10 and add to `l10`\n* **remove the integer part of `l10` aggressively**\n\nThis minimizes precison loss in the floating point math, gaining us a few precious digits at the end.\n\n**Without these tricks to improve precision we get off-by-one errors.**\n\n# Approach\n\nSee code and the docs for details.\n\n# Complexity\n- Time complexity: `O((right-left)*log(right))` for each value `x` in `left..right` we need to divde out factors of 2 and 5 in some of the loops, `O(log(x))` operations. The rest are floating-point math operations and machine-precision integer multiplications that can be done in `O(1)`\n\n- Space complexity: `O(1)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def abbreviateProduct(self, left: int, right: int) -> str:\n        # calc prod of l..r\n\n        # abbreviate as follows:\n        #      > count trailing zeros == C and remove them\n        #      > let remainder be d\n        #      > if d > 10 then report first and last five digits\n\n        # then print either (<=10 digits)eC\n        #       or (first5..last5)eC\n\n        # last five pretty easy, mod 1e5\n        # first five more interesting\n\n        # if we have Ae10 + Be9 + Ce8 + ...\n        # and we multiply by x\n        # we get Axe10 + Bxe9 + ...\n        # and the carry from D, E, F can roll up through A, B\n\n        # solutions include:\n        #      Python, Java: brute-force with arb. prec. ints\n        #      C++: roll your own\n        \n        # is there a clever way to get the first several digits?\n        # e.g. 1999 * 3 = 5997 via (2000-1)*3\n\n        # maybe groups of 10?\n        # if we know the product of a..b\n        #    then a+10..b+10 would be\n        #    (a+10)(a+1+10)..(b+10)\n        # a..b + 10*(a+1..b + a,a+2..b + ... + a..b-1) + 100*(all ways to drop 2) + 1000*(all ways to drop 3) + ...\n        # YIKES\n\n        # so manual multiply is probably the way to go barring some other innovations\n\n        # except manual multiply takes an order n*log10(n) digit number, does 3 mults on it, then sum\n        # for four passes over n*log10(n) digits O(n) times, yikes\n        # TOO EXPENSIVE\n\n        # so we need a math trick for this\n        #   last five digits are EZ\n\n        # first five digits are hard\n        # ... we\'re not expected to do the FFT multiply right? that would be very mean\n\n        # is there a faster way to get just a specific digit? For example what\'s the first digit?\n        # or can we get the number of digits?\n        #    yes, from log10 of the numbers summed\n        #\n        # we can get log10 of the number, and the floating point might give us what we need\n\n        twos = 0\n        fives = 0\n        for x in range(left, right+1):\n            while x % 2 == 0:\n                twos += 1\n                x //= 2\n            while x % 5 == 0:\n                fives += 1\n                x //= 5\n\n        C = min(twos, fives)\n\n        l10 = sum(log10(x) for x in range(left, right+1))\n        digits = int(l10 + 1)\n        \n        if digits - C <= 10:\n            # at most 10 digits besides trailing zeros: find the number via explicit multiply and divide-out-10s\n            p = 1\n            for x in range(left, right+1):\n                p *= x\n                while p % 10 == 0:\n                    p //= 10\n\n            return f"{p}e{C}"\n\n        # FIXED: lost some essential precision when the product is huge, e.g. l10 is 5000.something\n        # which means we dropped 3 digits from some of the values. So aggressively remove the integer\n        # part of the log10 so we retain as many digits as possible\n        l10 = 0\n        for x in range(left, right+1):\n            while x % 10 == 0: x //= 10\n            l10 += log10(x)\n            l10 -= int(l10)\n\n        # separate calculation of first and last 5 digits,\n        # potentially too many digits to divide out\n\n        # for first five:\n        #   log10(p) = log10(first*10**(digits-1) + second*10**(digits-2) + ...)\n        #             digits-1 + log10(first + second/10 + third/100 + ...)\n        #\n        #     so 10**(l10-int(l10)) == first+second/10 + ... fifth/1e4\n        #        (.................) * 1e4 is first*1e4 + .. + fifth   <- this is the number we want\n\n        firstFive = int(10**l10*1e4)\n\n        # fixed: last 5 are tricky\n        # we know that the last five are from factors that are not 2 or 5\n        # so what we need to do is get the digits other than 2 and 5\n        # multiply in excess factors of 2 and 5 to get all of them\n        # then mod 1e5\n        lastFive = right\n        for x in range(left, right):\n            # get last five digits if we drop all powers of 2 and 5\n            lastFive *= x\n            while lastFive % 2 == 0: lastFive //= 2\n            while lastFive % 5 == 0: lastFive //= 5\n\n            lastFive %= 100_000\n\n        # C handles 2**C and 5**C\n        #    if we have excess 2s and 5s we need to add them in\n        lastFive = (lastFive * pow(2, twos-C, 100_000)) % 100_000\n        lastFive = (lastFive * pow(5, fives-C, 100_000)) % 100_000\n\n        # FIXED: must print leading zeros in lastFive % 1e5\n        return f"{firstFive}...{lastFive:05d}e{C}"\n```
['Python3']