We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Product After K Increments

Difficulty: Medium

Problem Description

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. Since the answer may be very large, return it modulo 10^9 + 7. Note that you should maximize the product before taking the modulo.

Key Insights

  • Incrementing the smallest number in the array first maximizes the product.
  • Using a max heap (priority queue) allows for efficient retrieval and incrementing of the largest element.
  • The product is maximized when the increments are distributed among the smaller numbers to balance the values.

Space and Time Complexity

Time Complexity: O(k log n) - Each increment operation can take O(log n) time due to heap operations, and we may perform up to k increments. Space Complexity: O(n) - The space used by the heap to store the elements of the array.

Solution

To solve the problem, we can use a max heap (or a min heap with negative values) to efficiently get the largest element and increment it. The steps are as follows:

  1. Build a max heap from the given array.
  2. For each of the k increments, pop the largest element, increment it by 1, and push it back into the heap.
  3. After all increments, calculate the product of the elements in the heap.
  4. Return the product modulo 10^9 + 7.

Code Solutions

import heapq

def maxProduct(nums, k):
    mod = 10**9 + 7
    # Create a max heap by negating the values
    max_heap = [-num for num in nums]
    heapq.heapify(max_heap)
    
    # Perform k increments
    for _ in range(k):
        largest = -heapq.heappop(max_heap)  # Pop the largest element
        largest += 1  # Increment it
        heapq.heappush(max_heap, -largest)  # Push it back into the max heap

    # Calculate the product
    product = 1
    while max_heap:
        product = (product * -heapq.heappop(max_heap)) % mod

    return product
← Back to All Questions