Maximum Product After K Increments

To achieve the maximum product after at most k operations, we need to increment the smallest values in the array nums. The simplest approach to do this is to use a min-heap to keep track of the smallest values and increment them until we have used all k operations.

Here’s the code to do this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7

        # Convert nums into a min-heap
        heapq.heapify(nums)

        # Perform k increments on the smallest values
        for _ in range(k):
            smallest = heapq.heappop(nums)
            heapq.heappush(nums, smallest + 1)

        # Compute the product
        product = 1
        for num in nums:
            product = (product * num) % MOD

        return product

This code first transforms the nums list into a min-heap, so that the smallest value can be efficiently accessed and updated. Then it performs k increments on the smallest values in the heap, and finally calculates the product, taking the modulo as required.

The time complexity of this solution is (O(k \log n)), where (n) is the length of the nums array, as there are (k) increments, and each operation on the heap takes (O(\log n)) time.