Maximum Product After K Increments — Medium Problem & Solution

You may perform k operations; each adds 1 to any single element of nums.

Difficulty: Medium
Topics: Arrays, Greedy, Heap
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may perform k operations; each adds 1 to any single element of nums.

Return the maximum possible product of all elements after the k operations, modulo 10^9 + 7.

Example 1

Input: nums = [0,4], k = 5
Output: 20
Explanation: Spending all five on the 0 gives [5,4], a product of 20.

Example 2

Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Raising the 2 and then one 3 gives [6,4,3,3].

Example 3

Input: nums = [1], k = 3
Output: 4

Constraints

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
0 <= k <= 1000

How to solve Maximum Product After K Increments

Levelling up the smallest element is always optimal. Adding 1 to a value v scales the product by (v + 1) / v, which is largest when v is smallest — so a greedy that always feeds the minimum maximises the product.

Approach

Repeat k times: find the current minimum and increment it.
Multiply the final values together, reducing modulo 10^9 + 7 as you go.

Why it works

Exchange argument: if an optimal plan gives an increment to b while some a < b could take it instead, moving that increment to a changes the product by the factor ((a+1)·b) / (a·(b+1)), which exceeds 1 exactly when a < b. So no optimal plan ever prefers the larger element.

Complexity

Time — O(k · n) here; O((n + k) log n) with a heap
Space — O(n)

Pitfalls

Reducing modulo before comparing values would break the greedy — the modulo belongs only to the final product.
A zero in the array makes the product zero unless it is raised, which the greedy does first anyway.
Spreading increments evenly is not optimal when the values start far apart.

Reference solution

Python

from typing import List

def maximumProduct(nums: List[int], k: int) -> int:
    MOD = 1000000007
    a = list(nums)
    for _ in range(k):
        lo = 0
        for i in range(1, len(a)):
            if a[i] < a[lo]:
                lo = i
        a[lo] += 1
    product = 1
    for x in a:
        product = product * x % MOD
    return product

JavaScript

var maximumProduct = function(nums, k) {
    var MOD = 1000000007;
    var a = nums.slice();
    for (var t = 0; t < k; t++) {
        var lo = 0;
        for (var i = 1; i < a.length; i++) {
            if (a[i] < a[lo]) lo = i;
        }
        a[lo]++;
    }
    var product = 1;
    for (var j = 0; j < a.length; j++) product = (product * a[j]) % MOD;
    return product;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue