Skip to main content

Maximum Product After K Increments

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 the maximum product of nums after at most k operations.

Examples​

Example 1:

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:

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 <= 105
  • 0 <= nums[i] <= 106

Approach​

Use a Min-Heap: Convert the array into a min-heap to efficiently manage the smallest element. Perform Increments: For each of the k operations:

  • Extract the smallest element from the heap.
  • Increment this element by 1.
  • Push the incremented element back into the heap. Calculate the Product: After completing all increments, compute the product of all elements in the heap.

Solution​

Code in Different Languages​

C++ Solution​

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int maxProduct(vector<int>& nums, int k) {
const int MOD = 1e9 + 7;
priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.end());

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

long long product = 1;
while (!minHeap.empty()) {
product = (product * minHeap.top()) % MOD;
minHeap.pop();
}

return product;
}

int main() {
vector<int> nums1 = {0, 4};
int k1 = 5;
cout << maxProduct(nums1, k1) << endl; // Output: 20

vector<int> nums2 = {6, 3, 3, 2};
int k2 = 2;
cout << maxProduct(nums2, k2) << endl; // Output: 216

return 0;
}



Java Solution​

import java.util.PriorityQueue;

public class MaxProduct {
public static int maxProduct(int[] nums, int k) {
final int MOD = 1_000_000_007;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.add(num);
}

for (int i = 0; i < k; ++i) {
int minVal = minHeap.poll();
minHeap.add(minVal + 1);
}

long product = 1;
while (!minHeap.isEmpty()) {
product = (product * minHeap.poll()) % MOD;
}

return (int) product;
}

public static void main(String[] args) {
int[] nums1 = {0, 4};
int k1 = 5;
System.out.println(maxProduct(nums1, k1)); // Output: 20

int[] nums2 = {6, 3, 3, 2};
int k2 = 2;
System.out.println(maxProduct(nums2, k2)); // Output: 216
}
}


Python Solution​

import heapq

def maxProduct(nums, k):
MOD = 10**9 + 7
heapq.heapify(nums) # Turn nums into a min-heap

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

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

return product

# Example usage
print(maxProduct([0, 4], 5)) # Output: 20
print(maxProduct([6, 3, 3, 2], 2)) # Output: 216


Complexity Analysis​

Time Complexity: O(n+k∗logn)O(n+k*logn)​

Reason:O(n)O(n) for heapifying the array and O(k∗logn)O(k*logn) for k increment operations

Space Complexity: O(n)O(n)​

Reason: due to the storage required for the heap.