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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Product After K Increments

Number: 2329

Difficulty: Medium

Paid? No

Companies: Infosys

Problem Description

Given an array of non-negative integers and an integer k, you are allowed to perform at most k operations where in each operation you can increment any element by 1. The goal is to maximize the product of the array after these operations. Since the product can be very large, return it modulo 10^9 + 7.

Key Insights

  • It is optimal to increment the smallest element at every step, as balancing the values typically maximizes the overall product.
  • A min-heap (or priority queue) efficiently provides the smallest element for each increment operation.
  • Iteratively popping the smallest element, incrementing it, and pushing back into the heap ensures that the increments are used where they can contribute most to increasing the product.

Space and Time Complexity

Time Complexity: O((N + k) * log N) where N is the length of the nums array. Heapify takes O(N) and each of the k operations takes O(log N).
Space Complexity: O(N) due to the heap storage.

Solution

We use a min-heap (priority queue) to always access the smallest element. For each of the k operations, we pop the smallest element, increment it by 1, and then push it back into the heap. After using all k operations, we multiply all the elements together while taking the modulo 10^9 + 7. This ensures that we maximize the product by balancing the numbers.

Code Solutions

import heapq

MOD = 10**9 + 7

def maxProductAfterKIncrements(nums, k):
    # Convert the list into a min-heap.
    heapq.heapify(nums)
    
    # Perform k operations of incrementing the smallest element.
    while k > 0:
        # Pop the smallest element.
        smallest = heapq.heappop(nums)
        # Increment the smallest element.
        smallest += 1
        # Push the incremented element back to the heap.
        heapq.heappush(nums, smallest)
        k -= 1

    # Calculate product of all numbers with modulo.
    product = 1
    for num in nums:
        product = (product * num) % MOD
    return product

# Example usage:
print(maxProductAfterKIncrements([0, 4], 5))  # Output: 20
← Back to All Questions