Prices That Fade With Each Sale

Medium

A warehouse holds several kinds of goods: stock[i] is how many units of kind i it has right now. A wholesaler wants to buy exactly sales units, of any kinds. The wholesaler pays in an odd way: a unit is worth as many as there are units of that kind left in the warehouse **at the moment of the sale**. If the warehouse has 6 kettles, the first sells for 6, the next for 5, and so on. You may sell in any order. Find the largest possible revenue for sales units. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

stock=[4, 2], sales=3 → 9

Sell the first product three times: 4 + 3 + 2 = 9. Selling the second product for 2 at the last step gives the same total.

Example 2

stock=[3, 3, 1], sales=5 → 11

Sell for 3 and 3, then 2 and 2, and the last unit for 1: 3 + 3 + 2 + 2 + 1 = 11.

Example 3

stock=[1000000000], sales=1000000000 → 21

Constraints

1 ≤ len(stock) ≤ 10⁵
1 ≤ stock[i] ≤ 10⁹
1 ≤ sales ≤ min(sum(stock), 10⁹)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Math Binary Search Sorting Heap (Priority Queue)

Similar problems

Same Prizes, Different Tastes Medium Shrink the Squared Gaps Medium Level Out to a Palindrome Medium A Crew Levels a Hill Medium Growing Groups Without Repeats Hard

Input

stock=[4, 2], sales=3

Expected

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