Problem

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 _themaximum product of _nums _afterat 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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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 <= 10^5
  • 0 <= nums[i] <= 10^6

Solution

Method 1 – Greedy with Min-Heap

Intuition

To maximize the product, we should always increment the smallest element in the array. By always increasing the minimum, we ensure the product grows as much as possible at each step. This is efficiently done using a min-heap (priority queue).

Approach

  1. Insert all elements of nums into a min-heap.
  2. For k times:
    • Pop the smallest element, increment it by 1, and push it back.
  3. After all increments, multiply all elements in the heap to get the result.
  4. Return the product modulo 10^9 + 7.

Code

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

class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.end());
        while (k--) {
            int x = pq.top(); pq.pop();
            pq.push(x + 1);
        }
        long long ans = 1, mod = 1e9 + 7;
        while (!pq.empty()) {
            ans = ans * pq.top() % mod;
            pq.pop();
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import "container/heap"
type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}
func maximumProduct(nums []int, k int) int {
    h := IntHeap(nums)
    heap.Init(&h)
    for ; k > 0; k-- {
        x := heap.Pop(&h).(int)
        heap.Push(&h, x+1)
    }
    ans, mod := 1, int(1e9+7)
    for _, x := range h {
        ans = ans * x % mod
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public int maximumProduct(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : nums) pq.offer(x);
        while (k-- > 0) {
            pq.offer(pq.poll() + 1);
        }
        long ans = 1, mod = (long)1e9 + 7;
        while (!pq.isEmpty()) {
            ans = ans * pq.poll() % mod;
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.PriorityQueue
class Solution {
    fun maximumProduct(nums: IntArray, k: Int): Int {
        val pq = PriorityQueue(nums.asList())
        repeat(k) {
            pq.add(pq.poll() + 1)
        }
        var ans = 1L
        val mod = 1_000_000_007L
        while (pq.isNotEmpty()) {
            ans = ans * pq.poll() % mod
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import heapq
class Solution:
    def maximumProduct(self, nums: list[int], k: int) -> int:
        heapq.heapify(nums)
        for _ in range(k):
            x = heapq.heappop(nums)
            heapq.heappush(nums, x + 1)
        ans = 1
        mod = 10**9 + 7
        for x in nums:
            ans = ans * x % mod
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn maximum_product(nums: Vec<i32>, k: i32) -> i32 {
        let mut heap = nums.into_iter().map(Reverse).collect::<BinaryHeap<_>>();
        let mut k = k;
        while k > 0 {
            let Reverse(x) = heap.pop().unwrap();
            heap.push(Reverse(x + 1));
            k -= 1;
        }
        let mut ans = 1i64;
        let m = 1_000_000_007i64;
        while let Some(Reverse(x)) = heap.pop() {
            ans = ans * x as i64 % m;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    maximumProduct(nums: number[], k: number): number {
        const heap = [...nums];
        heap.sort((a, b) => a - b);
        for (let i = 0; i < k; ++i) {
            heap[0]++;
            let j = 0;
            while (j + 1 < heap.length && heap[j] > heap[j+1]) {
                [heap[j], heap[j+1]] = [heap[j+1], heap[j]];
                j++;
            }
        }
        let ans = 1, mod = 1e9 + 7;
        for (const x of heap) ans = ans * x % mod;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k log n + n log n), where n is the length of nums. Each increment is a heap operation.
  • 🧺 Space complexity: O(n), for the heap.