{"id":6376,"date":"2020-02-23T13:06:48","date_gmt":"2020-02-23T21:06:48","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6376"},"modified":"2020-02-23T13:33:42","modified_gmt":"2020-02-23T21:33:42","slug":"leetcode-1363-largest-multiple-of-three","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-1363-largest-multiple-of-three\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1363. Largest Multiple of Three"},"content":{"rendered":"\n

Given an integer array of digits<\/code>, return the largest multiple of three<\/strong> that can be formed by concatenating some of the given digits in any order.<\/p>\n\n\n\n

Since the answer may not fit in an integer data type, return the answer as a string.<\/p>\n\n\n\n

If there is no answer return an empty string.<\/p>\n\n\n\n

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

Input:<\/strong> digits = [8,1,9]\nOutput:<\/strong> \"981\"\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> digits = [8,6,7,1,0]\nOutput:<\/strong> \"8760\"\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> digits = [1]\nOutput:<\/strong> \"\"\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> digits = [0,0,0,0,0,0]\nOutput:<\/strong> \"0\"\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= digits.length <= 10^4<\/code><\/li>
  • 0 <= digits[i] <= 9<\/code><\/li>
  • The returning answer must not contain unnecessary leading zeros.<\/li><\/ul>\n\n\n\n
    Solution: Greedy + Math + Counting sort<\/p>\n\n\n\n
    Count the numbers of each digit.
    if sum % 3 == 0, we can use all digits.
    if sum % 1 == 0, we can remove one digits among {1, 4, 7} => sum % 3 == 0
    if sum % 2 == 0, we can remove one digits among {2, 5, 8} => sum % 3 == 0
    if sum % 2 == 0, we have to remove two digits among {1, 4, 7} => sum % 3 == 0
    if sum % 1 == 0, we have to remove two digits among {2, 5, 8} => sum % 3 == 0<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n) w\/ output, O(1) w\/o output<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string largestMultipleOfThree(vector& digits) {    \n    vector c(10);    \n    for (int d : digits) ++c[d];\n    \n    auto getNum = [&](const vector& ds) {\n      for (int d : ds) --c[d];\n      string ans;\n      for (int d = 9; d >= 1; --d) ans.append(c[d], '0' + d);\n      ans.append(ans.empty() ? min(1, c[0]) : c[0], '0');\n      return ans;\n    };\n    \n    const int r = accumulate(begin(digits), end(digits), 0) % 3;\n    vector> rs{{0, 3, 6, 9}, {1, 4, 7}, {2, 5, 8}};\n    \n    \/\/ Use all digitis.\n    if (r == 0) return getNum({});\n    \/\/ Remove one among {1, 4, 7}, {2, 5, 8}\n    for (int d : rs[r]) if (c[d]) return getNum({d});\n    \/\/ Remove two among {1, 4, 7}^2 (r = 2), {2, 5, 8}^2 (r = 1)\n    for (int d1 : rs[3 - r])\n      for (int d2 : rs[3 - r])\n        if (d1 == d2 && c[d1] > 1 || d1 != d2 && c[d1] && c[d2])\n          return getNum({d1, d2});\n    return \"\";\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    \n
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def largestMultipleOfThree(self, digits: List[int]) -> str:\n    c = collections.Counter(digits)\n    def getNum(ds):\n      ans = []\n      for d in ds: c[d] -= 1\n      for d in range(9, 0, -1): ans += [d] * c[d]\n      ans += [0] * min(1 if not ans else c[0], c[0])\n      return ''.join(map(str, ans))\n    rs = [[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]\n    r = sum(digits) % 3\n    if r == 0: return getNum([])\n    for d in rs[r]:\n      if c[d] > 0: return getNum([d])\n    for d1, d2 in zip(rs[3 - r], rs[3 - r]):\n      if d1 == d2 and c[d1] >= 2 or d1 != d2 and c[d1] and c[d2]:\n        return getNum([d1, d2])\n    return \"\"\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order. Since the answer…<\/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":[562,88,217,31],"class_list":["post-6376","post","type-post","status-publish","format-standard","hentry","category-math","tag-counting-sort","tag-greedy","tag-hard","tag-math","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6376","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=6376"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6376\/revisions"}],"predecessor-version":[{"id":6379,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6376\/revisions\/6379"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6376"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6376"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6376"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}