Skip to content

2233. Maximum Product After K Increments 👍

  • Time: $O(k\log n + n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int maximumProduct(vector<int>& nums, int k) {
    constexpr int kMod = 1'000'000'007;
    long ans = 1;
    priority_queue<int, vector<int>, greater<>> minHeap;

    for (const int num : nums)
      minHeap.push(num);

    for (int i = 0; i < k; ++i) {
      const int minNum = minHeap.top();
      minHeap.pop();
      minHeap.push(minNum + 1);
    }

    while (!minHeap.empty()) {
      ans *= minHeap.top(), minHeap.pop();
      ans %= kMod;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int maximumProduct(int[] nums, int k) {
    final int kMod = 1_000_000_007;
    long ans = 1;
    Queue<Integer> minHeap = new PriorityQueue<>();

    for (final int num : nums)
      minHeap.offer(num);

    for (int i = 0; i < k; ++i) {
      final int minNum = minHeap.poll();
      minHeap.offer(minNum + 1);
    }

    while (!minHeap.isEmpty()) {
      ans *= minHeap.poll();
      ans %= kMod;
    }

    return (int) ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maximumProduct(self, nums: list[int], k: int) -> int:
    kMod = 1_000_000_007
    ans = 1
    minHeap = nums.copy()
    heapq.heapify(minHeap)

    for _ in range(k):
      minNum = heapq.heappop(minHeap)
      heapq.heappush(minHeap, minNum + 1)

    while minHeap:
      ans *= heapq.heappop(minHeap)
      ans %= kMod

    return ans