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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maximumProduct(vector<int>& nums, int k) {\n        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.end());\n        while (k--) {\n            int x = pq.top(); pq.pop();\n            pq.push(x + 1);\n        }\n        long long ans = 1, mod = 1e9 + 7;\n        while (!pq.empty()) {\n            ans = ans * pq.top() % mod;\n            pq.pop();\n        }\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"import \"container/heap\"\ntype IntHeap []int\nfunc (h IntHeap) Len() int           { return len(h) }\nfunc (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }\nfunc (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }\nfunc (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }\nfunc (h *IntHeap) Pop() interface{} {\n    old := *h\n    x := old[len(old)-1]\n    *h = old[:len(old)-1]\n    return x\n}\nfunc maximumProduct(nums []int, k int) int {\n    h := IntHeap(nums)\n    heap.Init(&h)\n    for ; k > 0; k-- {\n        x := heap.Pop(&h).(int)\n        heap.Push(&h, x+1)\n    }\n    ans, mod := 1, int(1e9+7)\n    for _, x := range h {\n        ans = ans * x % mod\n    }\n    return ans\n}","lang":"go"},{"language":"Java","code":"import java.util.*;\nclass Solution {\n    public int maximumProduct(int[] nums, int k) {\n        PriorityQueue<Integer> pq = new PriorityQueue<>();\n        for (int x : nums) pq.offer(x);\n        while (k-- > 0) {\n            pq.offer(pq.poll() + 1);\n        }\n        long ans = 1, mod = (long)1e9 + 7;\n        while (!pq.isEmpty()) {\n            ans = ans * pq.poll() % mod;\n        }\n        return (int)ans;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"import java.util.PriorityQueue\nclass Solution {\n    fun maximumProduct(nums: IntArray, k: Int): Int {\n        val pq = PriorityQueue(nums.asList())\n        repeat(k) {\n            pq.add(pq.poll() + 1)\n        }\n        var ans = 1L\n        val mod = 1_000_000_007L\n        while (pq.isNotEmpty()) {\n            ans = ans * pq.poll() % mod\n        }\n        return ans.toInt()\n    }\n}","lang":"kotlin"},{"language":"Python","code":"import heapq\nclass Solution:\n    def maximumProduct(self, nums: list[int], k: int) -> int:\n        heapq.heapify(nums)\n        for _ in range(k):\n            x = heapq.heappop(nums)\n            heapq.heappush(nums, x + 1)\n        ans = 1\n        mod = 10**9 + 7\n        for x in nums:\n            ans = ans * x % mod\n        return ans","lang":"python"},{"language":"Rust","code":"use std::collections::BinaryHeap;\nuse std::cmp::Reverse;\nimpl Solution {\n    pub fn maximum_product(nums: Vec<i32>, k: i32) -> i32 {\n        let mut heap = nums.into_iter().map(Reverse).collect::<BinaryHeap<_>>();\n        let mut k = k;\n        while k > 0 {\n            let Reverse(x) = heap.pop().unwrap();\n            heap.push(Reverse(x + 1));\n            k -= 1;\n        }\n        let mut ans = 1i64;\n        let m = 1_000_000_007i64;\n        while let Some(Reverse(x)) = heap.pop() {\n            ans = ans * x as i64 %

Related Tags