[Python] math soluthion, explained
I will tidy up my code a bit later, for the moment what is important is idea. Basically, problem can be separated into 3 independet smaller problems:\n\n1. Find
I will tidy up my code a bit later, for the moment what is important is idea. Basically, problem can be separated into 3 independet smaller problems:\n\n1. Find number of trailing zeroes.\n2. Find last 5 digits which are not zeroes.\n3. Find first 5 digits.\n\nLet us deal with this problems one by one.\n1. To find number of trailing zeroes, we can use problem 172. Factorial Trailing Zeroes with modifications. We will find number of times divisors 2 and 5 met in our product and then choose the smallest one. I spend one fail attempt to catch the case like `L = R = 15`, then we have 1 five and 0 two.\n2. Find last 5 digits which are not zeroes: here what we need to do is to multiply all numbers, but also divide it by correct number of 5 and 2. To make our life easier I consider cases `R - L <= 30` separately where I just calculate product which is not very big by hands, python allows us to do it. In all other cases we can be sure that number of `5` in our prime factorization is smaller than number of `2`. I do not have strict proof, but it will help to make code a bit easier. So, each time we have number divisible by `5`, we divide it by `5` as many times as possible. Also we keep count of how many times we need to divide by `2` and when we reached limit, we stop dividing.\n3. Finally, how to find the first `5` digits of product. We will use logarithms and pray that we do not have rounding error. Indeed: `t = log10(L * (L+1) * ... * R) = log10(L) + ... + log10(R)`. What we need to take now is `10^(4 + {t})`, where `{t}` is fraction part. Luckily all tests were passed, probably because rounding error goes up and down and do not grow a lot.\n\n#### Complexity\nIt is `O(R - L)` for time because we need to work with modules and also with logarithms.\n\n#### Code\n```python\nfrom math import log10, floor, ceil\n\nclass Solution:\n    def abbreviateProduct(self, L, R):\n        def TZ(n, q):\n            ans = 0\n            while q <= n:\n                ans += n//q\n                q *= 5\n            return ans\n\n        c1 = TZ(R, 5) - TZ(L-1, 5)\n        c2 = TZ(R, 2) - TZ(L-1, 2)\n        tr_zeroes = min(c1, c2)\n\n        if R - L <= 30:\n            ans = 1\n            for i in range(L, R + 1):\n                ans *= i\n            ans_str = str(ans) if tr_zeroes == 0 else str(ans)[:-tr_zeroes]\n                \n            if len(ans_str) > 10:\n                return ans_str[:5] + "..." + ans_str[-5:] + "e" + str(tr_zeroes)\n            else:\n                return ans_str + "e" + str(tr_zeroes)\n            \n        else:\n            t = sum(log10(i) for i in range(L, R + 1))\n            tmp = t - floor(t)\n            first = floor(10**(tmp + 4))\n\n            last = 1\n            to_do = tr_zeroes\n            for i in range(L, R+1):\n                Q = i\n                while Q % 5 == 0: Q//=5\n                if Q % 2 == 0 and to_do > 0:\n                    Q = Q//2\n                    to_do -= 1\n                last = (last * Q) % 100000\n\n            return str(first) + "..." + "0" * (5 - len(str(last))) + str(last) + "e" + str(tr_zeroes)\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Math']