{"id":9640,"date":"2022-04-09T23:38:03","date_gmt":"2022-04-10T06:38:03","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9640"},"modified":"2022-04-09T23:38:40","modified_gmt":"2022-04-10T06:38:40","slug":"leetcode-2233-maximum-product-after-k-increments","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/priority-queue\/leetcode-2233-maximum-product-after-k-increments\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2233. Maximum Product After K Increments"},"content":{"rendered":"\n

You are given an array of non-negative integers nums<\/code> and an integer k<\/code>. In one operation, you may choose any<\/strong> element from nums<\/code> and increment<\/strong> it by 1<\/code>.<\/p>\n\n\n\n

Return the maximum<\/strong> product<\/strong> of <\/em>nums<\/code> after at most<\/strong> <\/em>k<\/code> operations. <\/em>Since the answer may be very large, return it modulo<\/strong> 109<\/sup> + 7<\/code>.<\/p>\n\n\n\n

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

Input:<\/strong> nums = [0,4], k = 5\nOutput:<\/strong> 20\nExplanation:<\/strong> Increment the first number 5 times.\nNow nums = [5, 4], with a product of 5 * 4 = 20.\nIt can be shown that 20 is maximum product possible, so we return 20.\nNote that there may be other ways to increment nums to have the maximum product.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [6,3,3,2], k = 2\nOutput:<\/strong> 216\nExplanation:<\/strong> Increment the second number 1 time and increment the fourth number 1 time.\nNow nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.\nIt can be shown that 216 is maximum product possible, so we return 216.\nNote that there may be other ways to increment nums to have the maximum product.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length, k <= 105<\/sup><\/code><\/li>
  • 0 <= nums[i] <= 106<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: priority queue<\/strong><\/h2>\n\n\n\n
    Always increment the smallest number. Proof?<\/p>\n\n\n\n
    Time complexity: O(klogn + nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximumProduct(vector& nums, int k) {\n    constexpr int kMod = 1e9 + 7;\n    priority_queue, greater> q(begin(nums), end(nums));\n    while (k--) {\n      const int n = q.top(); \n      q.pop();\n      q.push(n + 1);\n    }\n    long long ans = 1;\n    while (!q.empty()) {\n      ans *= q.top(); q.pop();\n      ans %= kMod;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1. Return the maximum product of nums after at most k operations. Since the answer may be very…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[674],"tags":[88,177,72,338],"class_list":["post-9640","post","type-post","status-publish","format-standard","hentry","category-priority-queue","tag-greedy","tag-medium","tag-priority-queue","tag-product","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9640","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=9640"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9640\/revisions"}],"predecessor-version":[{"id":9643,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9640\/revisions\/9643"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9640"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9640"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9640"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}