Sell Diminishing-Valued Colored Balls

You have an inventory of different colored balls, and there is a customer that wants orders balls of any color.

The customer values each colored ball based on the number of balls of that color you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is valued at 5; the value of balls decreases as you sell more of that color.

You are given an integer array inventory, where inventory[i] represents the number of balls of the i^th color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 10^9 + 7.

Example 1
Inputinventory = [2,5], orders = 4
Output14
Sell the 1st color 1 time for 2 and the 2nd color 3 times for 5 + 4 + 3, giving a maximum total value of 14.
Example 2
Inputinventory = [3,5], orders = 6
Output19
Sell the 1st color 2 times for 3 + 2 and the 2nd color 4 times for 5 + 4 + 3 + 2, giving a maximum total value of 19.

Constraints

  • 1 <= inventory.length <= 10^5
  • 1 <= inventory[i] <= 10^9
  • 1 <= orders <= min(sum(inventory[i]), 10^9)

Asked at 5 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate