{"id":9580,"date":"2022-03-21T05:21:32","date_gmt":"2022-03-21T12:21:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9580"},"modified":"2022-03-21T05:41:37","modified_gmt":"2022-03-21T12:41:37","slug":"leetcode-2208-minimum-operations-to-halve-array-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/heap\/leetcode-2208-minimum-operations-to-halve-array-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2208. Minimum Operations to Halve Array Sum"},"content":{"rendered":"\n

You are given an array nums<\/code> of positive integers. In one operation, you can choose any<\/strong> number from nums<\/code> and reduce it to exactly<\/strong> half the number. (Note that you may choose this reduced number in future operations.)<\/p>\n\n\n\n

Return the minimum<\/strong> number of operations to reduce the sum of <\/em>nums<\/code> by at least<\/strong> half.<\/em><\/p>\n\n\n\n

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

Input:<\/strong> nums = [5,19,8,1]\nOutput:<\/strong> 3\nExplanation:<\/strong> The initial sum of nums is equal to 5 + 19 + 8 + 1 = 33.\nThe following is one of the ways to reduce the sum by at least half:\nPick the number 19 and reduce it to 9.5.\nPick the number 9.5 and reduce it to 4.75.\nPick the number 8 and reduce it to 4.\nThe final array is [5, 4.75, 4, 1] with a total sum of 5 + 4.75 + 4 + 1 = 14.75. \nThe sum of nums has been reduced by 33 - 14.75 = 18.25, which is at least half of the initial sum, 18.25 >= 33\/2 = 16.5.\nOverall, 3 operations were used so we return 3.\nIt can be shown that we cannot reduce the sum by at least half in less than 3 operations.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [3,8,20]\nOutput:<\/strong> 3\nExplanation:<\/strong> The initial sum of nums is equal to 3 + 8 + 20 = 31.\nThe following is one of the ways to reduce the sum by at least half:\nPick the number 20 and reduce it to 10.\nPick the number 10 and reduce it to 5.\nPick the number 3 and reduce it to 1.5.\nThe final array is [1.5, 8, 5] with a total sum of 1.5 + 8 + 5 = 14.5. \nThe sum of nums has been reduced by 31 - 14.5 = 16.5, which is at least half of the initial sum, 16.5 >= 31\/2 = 16.5.\nOverall, 3 operations were used so we return 3.\nIt can be shown that we cannot reduce the sum by at least half in less than 3 operations.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 105<\/sup><\/code><\/li>
  • 1 <= nums[i] <= 107<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Greedy + PriorityQueue\/Max Heap<\/strong><\/h2>\n\n\n\n
    Always half the largest number, put all the numbers onto a max heap (priority queue), extract the largest one, and put reduced number back.<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int halveArray(vector& nums) {\n    double sum = accumulate(begin(nums), end(nums), 0.0);\n    priority_queue q;\n    for (int num : nums) q.push(num);\n    int ans = 0;\n    for (double cur = sum; cur > sum \/ 2; ++ans) {    \n      double num = q.top(); q.pop();\n      cur -= num \/ 2;\n      q.push(num \/ 2);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an array nums of positive integers. In one operation, you can choose any number from nums and reduce it to exactly half the number. (Note that you may choose this…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71],"tags":[88,73,177,377,382],"class_list":["post-9580","post","type-post","status-publish","format-standard","hentry","category-heap","tag-greedy","tag-heap","tag-medium","tag-onlogn","tag-priority_queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9580","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=9580"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9580\/revisions"}],"predecessor-version":[{"id":9582,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9580\/revisions\/9582"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9580"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9580"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9580"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}