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 large, return it modulo 109 + 7
.
Example 1:
Input: nums = [0,4], k = 5 Output: 20 Explanation: Increment the first number 5 times. Now nums = [5, 4], with a product of 5 * 4 = 20. It can be shown that 20 is maximum product possible, so we return 20. Note that there may be other ways to increment nums to have the maximum product.
Example 2:
Input: nums = [6,3,3,2], k = 2 Output: 216 Explanation: Increment the second number 1 time and increment the fourth number 1 time. Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216. It can be shown that 216 is maximum product possible, so we return 216. Note that there may be other ways to increment nums to have the maximum product.
Constraints:
1 <= nums.length, k <= 105
0 <= nums[i] <= 106
Solution: priority queue
Always increment the smallest number. Proof?
Time complexity: O(klogn + nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int maximumProduct(vector<int>& nums, int k) { constexpr int kMod = 1e9 + 7; priority_queue<int, vector<int>, greater<int>> q(begin(nums), end(nums)); while (k--) { const int n = q.top(); q.pop(); q.push(n + 1); } long long ans = 1; while (!q.empty()) { ans *= q.top(); q.pop(); ans %= kMod; } return ans; } }; |