AlgorithmsAmazonArraysData StructuresGreedyMedium DifficultyProgramming InterviewsPython

# [LeetCode 1648] Sell Diminishing-Valued Colored Balls

References:

• https://leetcode.com/problems/sell-diminishing-valued-colored-balls/
• https://stackoverflow.com/questions/10882645/is-there-a-faster-way-to-sum-up-an-arithmetic-sequence-of-numbers-in-python

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

The customer weirdly values the colored balls. Each colored ball’s value is 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 then valued at `5` (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, `inventory`, where `inventory[i]` represents the number of balls of the `ith` 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 `109 + 7`.

Example 1:

```Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.
```

Example 2:

```Input: inventory = [3,5], orders = 6
Output: 19
Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.
```

Example 3:

```Input: inventory = [2,8,4,10,6], orders = 20
Output: 110
```

Example 4:

```Input: inventory = , orders = 1000000000
Output: 21
Explanation: Sell the 1st color 1000000000 times for a total value of 500000000500000000. 500000000500000000 modulo 109 + 7 = 21.
```

Constraints:

• `1 <= inventory.length <= 105`
• `1 <= inventory[i] <= 109`
• `1 <= orders <= min(sum(inventory[i]), 109)`
```class Solution:
def maxProfit(self, inventory: List[int], orders: int) -> int:
inventory.sort(reverse=True)
inventory.append(0)
profit = 0
width = 1
for i in range(len(inventory)-1):
if inventory[i] > inventory[i+1]:
if width * (inventory[i] - inventory[i+1]) < orders:
profit += width * self.sumRange(inventory[i+1]+1, inventory[i])
orders -= width * (inventory[i] - inventory[i+1])
else:
whole, remaining = divmod(orders, width)
profit += width * self.sumRange(inventory[i]-whole+1, inventory[i])
profit += remaining * (inventory[i]-whole)
break
width += 1
return profit % (10**9 + 7)

def sumRange(self, lo, hi):
# inclusive lo and hi
return (hi * (hi+1)) // 2 - (lo * (lo-1)) // 2```

Previous Post

Next article