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
. Note that you should maximize the product before taking the modulo.
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
Similar Questions:
- Minimum Size Subarray Sum (Medium)
- Minimum Increment to Make Array Unique (Medium)
- Minimum Operations to Make the Array Increasing (Easy)
// OJ: https://leetcode.com/problems/maximum-product-after-k-increments/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int maximumProduct(vector<int>& A, int k) {
long mod = 1e9 + 7, ans = 1;
priority_queue<int, vector<int>, greater<>> pq(begin(A), end(A));
while (k--) {
int u = pq.top(), d = 1;
pq.pop();
pq.push(u + 1);
}
while (pq.size()) {
ans = ans * pq.top() % mod;
pq.pop();
}
return ans;
}
};
// OJ: https://leetcode.com/problems/maximum-product-after-k-increments/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int maximumProduct(vector<int>& A, int k) {
long mod = 1e9 + 7, ans = 1, L = 0, R = LONG_MAX, r = 0;
sort(begin(A), end(A));
while (L <= R) { // After the binary search, R is the maximum number such that if we turn all A[i] < R to R, we take no more than `k` increments
long M = L + (R - L) / 2, used = 0;
for (int n : A) {
used += max(0L, M - n);
if (used > k) break;
}
if (used <= k) {
L = M + 1;
r = k - used; // `r` is the remainder increments
} else R = M - 1;
}
for (int n : A) {
int diff = min((long)k, max(0L, R - n));
if (r) diff++, r--;
k -= diff;
ans = ans * (n + diff) % mod;
}
return ans;
}
};
// OJ: https://leetcode.com/problems/maximum-product-after-k-increments/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
void fillK(vector<int> &A, int k) {
long N = A.size(), sum = 0, i = 0;
while (i < N && A[i] * i - sum <= k) sum += A[i++]; // If we bump `A[0]~A[i-1]` to be `A[i]`, we need `A[i] * i - (A[0]+...+A[i-1])` increments which should be no more than `k`
int h = (sum + k) / i, r = (sum + k) % i; // We split `sum + k` heights among `A[0]~A[i-1]` `i` elements.
for (int j = 0; j < i; ++j) {
A[j] = h;
if (j < r) A[j]++;
}
}
public:
int maximumProduct(vector<int>& A, int k) {
long mod = 1e9 + 7, ans = 1;
sort(begin(A), end(A));
fillK(A, k);
for (int n : A) ans = ans * n % mod;
return ans;
}
};
https://leetcode.com/problems/maximum-product-after-k-increments/discuss/1937658