569. Boost the Product
You are given an array nums of non-negative integers and a budget of k upgrades. One upgrade picks any single position and adds exactly 1 to the value stored there; the same position may be upgraded several times. All k upgrades must be used.
After spending the upgrades, take the product of every element of the array. Choose the upgrades so that this product is as large as possible, and return that maximum product modulo 1000000007. Compare products by their true integer values, not by their remainders; only the value you return is reduced. If the best achievable product is 0 (some element is still 0 after all upgrades), return 0.
Expected complexity: O((n + k) log n) time, O(n) space.
Example 1
- Input:
- nums = [3,1,2], k = 3
- Output:
- 27
- Explanation:
Upgrade the smallest each time: [3,2,2], then [3,3,2], then [3,3,3], whose product is 27.
Example 2
- Input:
- nums = [0,4], k = 1
- Output:
- 4
- Explanation:
The only sensible upgrade is the 0, giving [1,4] with product 4.
Example 3
- Input:
- nums = [0,0,5], k = 1
- Output:
- 0
- Explanation:
One zero remains no matter what, so the product is 0.
Constraints
1 ≤ nums.length ≤ 1000000 ≤ nums[i] ≤ 1060 ≤ k ≤ 100000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O((n + k) log n)
- Space
- O(n)