Question

2233. Maximum Product After K Increments

中文文档

Description

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

Solutions

Solution 1

class Solution:
  def maximumProduct(self, nums: List[int], k: int) -> int:
    heapify(nums)
    for _ in range(k):
      heappush(nums, heappop(nums) + 1)
    ans = 1
    mod = 10**9 + 7
    for v in nums:
      ans = (ans * v) % mod
    return ans

class Solution {
  private static final int MOD = (int) 1e9 + 7;

  public int maximumProduct(int[] nums, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<>();
    for (int v : nums) {
      q.offer(v);
    }
    while (k-- > 0) {
      q.offer(q.poll() + 1);
    }
    long ans = 1;
    while (!q.isEmpty()) {
      ans = (ans * q.poll()) % MOD;
    }
    return (int) ans;
  }
}

class Solution {
public:
  int maximumProduct(vector<int>& nums, int k) {
    int mod = 1e9 + 7;
    make_heap(nums.begin(), nums.end(), greater<int>());
    while (k--) {
      pop_heap(nums.begin(), nums.end(), greater<int>());
      ++nums.back();
      push_heap(nums.begin(), nums.end(), greater<int>());
    }
    long long ans = 1;
    for (int v : nums) ans = (ans * v) % mod;
    return ans;
  }
};

func maximumProduct(nums []int, k int) int {
  h := hp{nums}
  for heap.Init(&h); k > 0; k-- {
    h.IntSlice[0]++
    heap.Fix(&h, 0)
  }
  ans := 1
  for _, v := range nums {
    ans = (ans * v) % (1e9 + 7)
  }
  return ans
}

type hp struct{ sort.IntSlice }

func (hp) Push(any)   {}
func (hp) Pop() (_ any) { return }

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumProduct = function (nums, k) {
  const n = nums.length;
  let pq = new MinPriorityQueue();
  for (let i = 0; i < n; i++) {
    pq.enqueue(nums[i]);
  }
  for (let i = 0; i < k; i++) {
    pq.enqueue(pq.dequeue().element + 1);
  }
  let ans = 1;
  const limit = 10 ** 9 + 7;
  for (let i = 0; i < n; i++) {
    ans = (ans * pq.dequeue().element) % limit;
  }
  return ans;
};