{"id":9267,"date":"2021-12-26T14:40:57","date_gmt":"2021-12-26T22:40:57","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9267"},"modified":"2021-12-30T03:05:40","modified_gmt":"2021-12-30T11:05:40","slug":"leetcode-2117-abbreviating-the-product-of-a-range","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-2117-abbreviating-the-product-of-a-range\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2117. Abbreviating the Product of a Range"},"content":{"rendered":"\n

You are given two positive integers left<\/code> and right<\/code> with left <= right<\/code>. Calculate the product<\/strong> of all integers in the inclusive<\/strong> range [left, right]<\/code>.<\/p>\n\n\n\n

Since the product may be very large, you will abbreviate<\/strong> it following these steps:<\/p>\n\n\n\n

  1. Count all trailing<\/strong> zeros in the product and remove<\/strong> them. Let us denote this count as C<\/code>.
    • For example, there are 3<\/code> trailing zeros in 1000<\/code>, and there are 0<\/code> trailing zeros in 546<\/code>.<\/li><\/ul><\/li>
    • Denote the remaining number of digits in the product as d<\/code>. If d > 10<\/code>, then express the product as <pre>...<suf><\/code> where <pre><\/code> denotes the first<\/strong> 5<\/code> digits of the product, and <suf><\/code> denotes the last<\/strong> 5<\/code> digits of the product after<\/strong> removing all trailing zeros. If d <= 10<\/code>, we keep it unchanged.
      • For example, we express 1234567654321<\/code> as 12345...54321<\/code>, but 1234567<\/code> is represented as 1234567<\/code>.<\/li><\/ul><\/li>
      • Finally, represent the product as a string<\/strong> \"<pre>...<suf>eC\"<\/code>.
        • For example, 12345678987600000<\/code> will be represented as \"12345...89876e5\"<\/code>.<\/li><\/ul><\/li><\/ol>\n\n\n\n

          Return a string denoting the abbreviated product<\/strong> of all integers in the inclusive<\/strong> range<\/em> [left, right]<\/code>.<\/p>\n\n\n\n

          Example 1:<\/strong><\/p>\n\n\n\n

          Input:<\/strong> left = 1, right = 4\nOutput:<\/strong> \"24e0\"\nExplanation:<\/strong>\nThe product is 1 \u00d7 2 \u00d7 3 \u00d7 4 = 24.\nThere are no trailing zeros, so 24 remains the same. The abbreviation will end with \"e0\".\nSince the number of digits is 2, which is less than 10, we do not have to abbreviate it further.\nThus, the final representation is \"24e0\". \n<\/pre>\n\n\n\n
          Example 2:<\/strong><\/p>\n\n\n\n
          Input:<\/strong> left = 2, right = 11\nOutput:<\/strong> \"399168e2\"\nExplanation:<\/strong>\nThe product is 39916800.\nThere are 2 trailing zeros, which we remove to get 399168. The abbreviation will end with \"e2\".\nThe number of digits after removing the trailing zeros is 6, so we do not abbreviate it further.\nHence, the abbreviated product is \"399168e2\".  \n<\/pre>\n\n\n\n
          Example 3:<\/strong><\/p>\n\n\n\n
          \"\"\/<\/figure>\n\n\n\n
          Input:<\/strong> left = 999998, right = 1000000\nOutput:<\/strong> \"99999...00002e6\"\nExplanation:<\/strong>\nThe above diagram shows how we abbreviate the product to \"99999...00002e6\".\n- It has 6 trailing zeros. The abbreviation will end with \"e6\".\n- The first 5 digits are 99999.\n- The last 5 digits after removing trailing zeros is 00002.\n<\/pre>\n\n\n\n
          Constraints:<\/strong><\/p>\n\n\n\n
          • 1 <= left <= right <= 106<\/sup><\/code><\/li><\/ul>\n\n\n\n
            Solution: Prefix + Suffix<\/strong><\/h2>\n\n\n\n
            Since we only need the first 5 digits and last 5 digits, we can compute prefix and suffix separately with 15+ effective digits. Note, if using long\/int64 with (18 – 6) = 12 effective digits, it may fail on certain test cases. Thus, here we use Python with 18 effective digits.<\/p>\n\n\n\n
            Time complexity: O(mlog(right)) where m = right – left + 1
            Space complexity: O(1)<\/p>\n\n\n\n
            \n
            Python3<\/h2>\n
            \n\n
            \n# Author: Huahua\nclass Solution:\n  def abbreviateProduct(self, left: int, right: int) -> str:\n    kMax = 10 ** 18\n    prefix = 1\n    suffix = 1\n    c = 0\n    for i in range(left, right + 1):\n      prefix *= i\n      while prefix >= kMax:\n        prefix \/\/= 10\n      suffix *= i\n      while suffix % 10 == 0: \n        suffix \/\/= 10\n        c += 1\n      suffix %= kMax\n    \n    p, s = str(prefix), str(suffix)\n    return (s if len(s) <= 10 else p[:5] + \"...\" + s[-5:]) + \"e\" + str(c);\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
            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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[217,31],"class_list":["post-9267","post","type-post","status-publish","format-standard","hentry","category-math","tag-hard","tag-math","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9267"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9267\/revisions"}],"predecessor-version":[{"id":9283,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9267\/revisions\/9283"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}