\n**PLEASE UPVOTE if you like** \uD83D\uDE01 **If you have any question, feel free to ask.** \n
\n\nThere is no free lunch, both logarithmic sum and scientific notation will definitely lose accuracy. we can only discard the last digits and keep the most important prefix as many as possible, actually `float` even `double` are also imprecise.\n```\nTime Complexity: O(N)\nSpace Complexity: O(1)\n```\n\n* **Solution 1: use float or double to record prefix, inspired by scientific notation**\n\t* keep `0.1 <= prod < 1.0`, so `len(str(int(prod * 100000))) == 5`, just like **scientific notation**\n\t\t* so we can easily get `pre` via `pre = str(int(prod * 100000))`\n\t* `org_digits` is the number of digits of the original very very large product number, `zeros` is the number of its trailing zeros, so that `org_digits - zeros` is the number of its actual non-zero digits.\n\t* The error of `suf` can only come from the trailing zeros.\n\t\t* Although we remove all of the trailing zeros every time and then take the modulus, but 2 and 5 as thedivision of suf may squeeze the effective digit length.\n\t\t* so if we want to keep the exactly accurate last 5 Digits, we need to increase the digit length.\n\t\t* Since `n` is less than or equal to `10 ** 4`, there are no more than 5 trailing zeros that can be eliminated at one time. At this time, `n = 5 ** 5`, and the eliminated invalidity factor is `2 ** 5 = 32`, so we waste up to 5 digits for recording useless information at one time, so `suf %= 10 ** 14` is large enough to keep accurate 5 digits of `suf`.\n\t\t* Another reason we chose `10 ** 14` is that `(10 ** 14) * (10 ** 4) = 10 ** 18` is in the range of `int64`, so it can be easily migrated to other programming languages such as Java and C++.\n\n\n\t\t**Python**\n\t\t```\n\t\tclass Solution(object):\n\t\t\tdef abbreviateProduct(self, left, right):\n\t\t\t\tprod, suf, zeros, org_digits = 1.0, 1, 0, 0\n\t\t\t\tfor n in range(left, right + 1):\n\t\t\t\t\tprod *= n\n\t\t\t\t\twhile prod >= 1: # keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5\n\t\t\t\t\t\tprod /= 10\n\t\t\t\t\t\torg_digits += 1 # add 1 while remove 1 digit\n\t\t\t\t\tsuf *= n\n\t\t\t\t\twhile suf % 10 == 0: # count and remove the trailing zeros\n\t\t\t\t\t\tzeros += 1\n\t\t\t\t\t\tsuf //= 10\n\t\t\t\t\tif suf > 10 ** 14:\n\t\t\t\t\t\tsuf %= 10 ** 14\n\t\t\t\tif org_digits - zeros <= 10:\n\t\t\t\t\treturn str(int(prod * (10 ** (org_digits - zeros)) + 0.5)) + \'e\' + str(zeros)\n\t\t\t\telse:\n\t\t\t\t\t# you may find that I add 0.5 before cast to int above, but not here.\n\t\t\t\t\t# It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual\n\t\t\t\t\t# value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.\n\t\t\t\t\t# However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not\n\t\t\t\t\t# error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?\n\t\t\t\t\treturn str(int(prod * 100000)) + \'...\' + (\'0000\' + str(suf))[-5:] + \'e\' + str(zeros)\n\t\t```\n\t\t**C++**\n\t\t```\n\t\tclass Solution {\n\t\tpublic:\n\t\t\tstring abbreviateProduct(int left, int right) {\n\t\t\t\tlong long suf = 1;\n\t\t\t\tint zeros = 0, org_digits = 0;\n\t\t\t\tdouble prod = 1.0;\n\t\t\t\tfor (int n = left; n <= right; n ++) {\n\t\t\t\t\tprod *= n;\n\t\t\t\t\twhile (prod >= 1.0) { // keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5\n\t\t\t\t\t\tprod /= 10.0;\n\t\t\t\t\t\torg_digits ++; // add 1 while remove 1 digit\n\t\t\t\t\t}\n\t\t\t\t\tsuf *= n;\n\t\t\t\t\twhile (suf % 10 == 0) { // count and remove the trailing zeros\n\t\t\t\t\t\tzeros ++;\n\t\t\t\t\t\tsuf /= 10;\n\t\t\t\t\t}\n\t\t\t\t\tif (suf > pow(10, 14)) suf %= (long long)pow(10, 14);\n\t\t\t\t}\n\t\t\t\tif (org_digits - zeros <= 10) {\n\t\t\t\t\treturn to_string((long long)(prod * pow(10, org_digits - zeros) + 0.5)) + \'e\' + to_string(zeros);\n\t\t\t\t} else {\n\t\t\t\t\t// you may find that I add 0.5 before cast to int above, but not here.\n\t\t\t\t\t// It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual\n\t\t\t\t\t// value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.\n\t\t\t\t\t// However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not\n\t\t\t\t\t// error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?\n\t\t\t\t\tstring str_suf = "0000" + to_string(suf);\n\t\t\t\t\treturn to_string((int)(prod * 100000)) + "..." + str_suf.substr(str_suf.length() - 5) + \'e\' + to_string(zeros);\n\t\t\t\t}\n\t\t\t}\n\t\t};\n\t\t```\n\t\t**Java**\n\t\t```\n\t\tclass Solution {\n\t\t\tpublic String abbreviateProduct(int left, int right) {\n\t\t\t\tlong suf = 1;\n\t\t\t\tint zeros = 0, org_digits = 0;\n\t\t\t\tdouble prod = 1.0;\n\t\t\t\tfor (int n = left; n <= right; n ++) {\n\t\t\t\t\tprod *= n;\n\t\t\t\t\twhile (prod >= 1.0) { // keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5\n\t\t\t\t\t\tprod /= 10.0;\n\t\t\t\t\t\torg_digits ++; // add 1 while remove 1 digit\n\t\t\t\t\t}\n\t\t\t\t\tsuf *= n;\n\t\t\t\t\twhile (suf % 10 == 0) { // count and remove the trailing zeros\n\t\t\t\t\t\tzeros ++;\n\t\t\t\t\t\tsuf /= 10;\n\t\t\t\t\t}\n\t\t\t\t\tif (suf > Math.pow(10, 14)) suf %= (long)Math.pow(10, 14);\n\t\t\t\t}\n\t\t\t\tif (org_digits - zeros <= 10) {\n\t\t\t\t\treturn (long)(prod * Math.pow(10, org_digits - zeros) + 0.5) + "e" + zeros;\n\t\t\t\t} else {\n\t\t\t\t\t// you may find that I add 0.5 before cast to int above, but not here.\n\t\t\t\t\t// It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual\n\t\t\t\t\t// value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.\n\t\t\t\t\t// However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not\n\t\t\t\t\t// error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?\n\t\t\t\t\tString str_suf = "0000" + Long.toString(suf);\n\t\t\t\t\treturn (int)(prod * 100000) + "..." + str_suf.substring(str_suf.length() - 5) + \'e\' + zeros;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\t```\n\n* **Solution 2\uFF1Ause int64 to record prefix**\n\n\t* `pre `and `suf` retain at most 13 digits each\n\t* They update separately\n\t* at any time, once the trailing `0` appears it will not disappear.\n\t\t* so we count trailing zeros in `suf` immediately via `zeros += 1`, then remove them from suf via `suf //= 10`\n\t* My naive motivation is as long as `MAX` is large enough, the code above would work well.\n\t\t```\n\t\tclass Solution(object):\n\t\t\tdef abbreviateProduct(self, left, right):\n\t\t\t\tMAX = 10 ** 13\n\t\t\t\tpre, suf, zeros, org_digits = 1, 1, 0, 0\n\t\t\t\tfor n in range(left, right + 1):\n\t\t\t\t\tpre *= n # update pre\n\t\t\t\t\tsuf *= n # update suf\n\t\t\t\t\twhile suf % 10 == 0: # count and remove the trailing zeros\n\t\t\t\t\t\tzeros += 1\n\t\t\t\t\t\tsuf //= 10\n\t\t\t\t\tif suf > MAX: # retain at most 13 digits\n\t\t\t\t\t\tsuf %= MAX\n\t\t\t\t\twhile pre > MAX: # retain at most 13 digits\n\t\t\t\t\t\tif org_digits == 0:\n\t\t\t\t\t\t\torg_digits = 13\n\t\t\t\t\t\tpre //= 10\n\t\t\t\t\t\torg_digits += 1\n\t\t\t\tif len(str(suf)) <= 10 and org_digits - zeros <= 10:\n\t\t\t\t\treturn str(suf)[:10] + \'e\' + str(zeros)\n\t\t\t\telse:\n\t\t\t\t\treturn str(pre)[:5] + \'...\' + str(suf)[-5:] + \'e\' + str(zeros)\n\t\t```\n\t\n\n* **Solution 3: use logarithmic sum to record prefix**\n\t* I noticed a popular solution from another perspective using logarithmic sum, but since the time complexity is still `O(R - L)`, maybe it is no need to waste code to deal with 2 and 5 specially, removing them can make the code and the idea concise a lot.\n\t* the key idea is the logarithm of the product of a set of numbers is equal to the sum of the logarithms of the set of numbers.\n\t\t* `log(a * b * c) = log(a) + log(b) + log(c)`\n\t* Although the multiplication of `1` to `10 ** 6` is very very large, far exceeding the range of any basic data type in the programming language, its logarithm base `10` is only `5565702.91719`\n\t\t* however there is no free lunch, it must also loss precision when you recover the original large number N via power of `10`, like the 2 solutions above.\n\t* The integer part of the logarithm of a number N records the scale of N, and the decimal part records the precision of N.\n\t\t* for example, `log10(37968) = 4.579417720873264`\n\t\t\t* `10 ** 0.579417720873264 = 3.7968000000000024`\n\t\t\t* `10 ** 4 = 10000`\n\t\t\t* `37968 = 10 ** 4.579417720873264 = (10 ** 4) * (10 ** 0.579417720873264)`\n\t\t* Since `10 ** 0 = 1` and `10 ** 1 == 10`, for any `0 < x < 1`, `1 < 10 ** x < 10`, that also means so `len(str(int((10 ** x) * 100000))) == 5`\n\t\t* **Essentially this is the same as scientific notation.**\n\t\t```\n\t\tclass Solution(object):\n\t\t\tdef abbreviateProduct(self, left, right):\n\t\t\t\tsuf, zeros, log_sum, prod, org_digits = 1, 0, 0, 1.0, 0\n\t\t\t\tfor n in range(left, right + 1):\n\t\t\t\t\tlog_sum += math.log10(n)\n\t\t\t\t\tsuf *= n\n\t\t\t\t\twhile suf % 10 == 0: # count and remove the trailing zeros\n\t\t\t\t\t\tzeros += 1\n\t\t\t\t\t\tsuf //= 10\n\t\t\t\t\tif suf > 10 ** 8:\n\t\t\t\t\t\tsuf %= 10 ** 8\n\t\t\t\t\tprod *= n\n\t\t\t\t\twhile prod > 1.0:\n\t\t\t\t\t\torg_digits += 1\n\t\t\t\t\t\tprod /= 10\n\t\t\t\tif org_digits - zeros <= 10:\n\t\t\t\t\tpre = 10 ** (log_sum - int(log_sum) + 9)\n\t\t\t\t\treturn str(pre)[:max(1, org_digits - zeros)] + \'e\' + str(zeros)\n\t\t\t\telse:\n\t\t\t\t\tpre = 10 ** (log_sum - int(log_sum) + 4)\n\t\t\t\t\treturn str(pre)[:5] + \'...\' + str(suf)[-5:] + \'e\' + str(zeros)\n\t\t```\n\n\n**PLEASE UPVOTE if you like \uD83D\uDE01 If you have any question, feel free to ask.**

Abbreviating the Product of a Range

Problem Description

Problem Description

Answer Panel