Statement▼
You are given an array, nums, consisting of non-negative integers, and an integer k representing the maximum number of allowed operations.
In each operation, you may select any element in nums and increment it by k such operations.
Your task is to maximize the product of all elements in the array after performing up to k operations. As the resulting product can be very large, return the product modulo
Note: Ensure that the product is maximized before applying the modulo operation.
Constraints:
1≤ nums.length,k≤103 0≤ nums[i]≤103
Solution
The core intuition behind the solution is to maximize the product of the nums elements by distributing the k increment operations in a way that promotes balance among the values. In multiplication, products are higher when numbers are close in value. For example,
Multiplication favors numbers that are close in value, so the goal is to balance out
numsby incrementing the smallest elements first.Incrementing smaller numbers contributes more to the overall product than incrementing larger ones, making them the most effective targets for
koperations.
This strategy uses the top k elements pattern with a min heap, allowing quick access to the current smallest number. All elements from nums are inserted into the heap. For each k operations, we extract the minimum element, increment it by
In some cases, the smallest element may be much smaller than the rest of the array—for example, in k operations may be applied solely to that minimum element, progressively closing the gap and improving the product.
After performing all k increments, the product of all heap elements is computed and returned modulo
Now, let’s look at the solution steps below:
We initialize a variable
mod = 109+ 7to handle modulo operations for the overflow issues.We initialize a min heap with all the elements of
nums.To evenly distribute increments, we perform
koperations by:Popping the
smallestelement from the heap.Incrementing the
smallestelement by1 .Pushing the
smallestelement back into the heap.
We initialize a variable,
result = 1, to store the maximized product of all elements innums.After
kincrements, we compute the product modulo of all elements in the heap by:Repeatedly popping elements from the heap.
Multiply them with the
result, taking the modulo withmodat each step to prevent overflow.
We return the final value of the
result, which represents the maximum product modulo.
Let’s look at the following illustration to get a better understanding of the solution: