Increments for the Biggest Product

Medium

You get an array of non-negative integers values and an integer raises. In one step you may pick any element and add 1 to it. You can make at most raises steps in total, and the same element may be raised many times. Return the largest product of all elements you can reach. The answer can be huge, so return it modulo 10⁹ + 7. Maximize the true product and only take the remainder at the end.

Example 1

values=[1, 7], raises=4 → 35

Give all four increments to the 1: [5, 7], product 35. Any other split does worse, e.g. [3, 9] gives only 27.

Example 2

values=[2, 0, 3], raises=3 → 18

Raise the 0 to 2, then give the last increment to one of the 2s: [3, 2, 3] or [2, 3, 3], product 18.

Example 3

values=[4], raises=6 → 10

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ raises ≤ 10⁵
0 ≤ values[i] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Heap (Priority Queue)

Similar problems

Studios for Recording Sessions Medium Jobs With a Cooldown Medium Sorted Into Runs of Three Medium Spread Out the Labels Medium Splicing Ropes Medium

Input

values=[1, 7], raises=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 88 tests on the server, hidden ones included.