In this guide, you will get 1648. Sell Diminishing-Valued Colored Balls LeetCode Solution with the best time and space complexity. The solution to Sell Diminishing-Valued Colored Balls problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 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.
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.
1648. Sell Diminishing-Valued Colored Balls LeetCode Solution in C++
class Solution {
public:
int maxProfit(vector<int>& inventory, int orders) {
constexpr int kMod = 1'000'000'007;
long ans = 0;
long largestCount = 1;
ranges::sort(inventory, greater<>());
for (int i = 0; i < inventory.size(); ++i, ++largestCount)
if (i == inventory.size() - 1 || inventory[i] > inventory[i + 1]) {
// If we are at the last inventory, or inventory[i] > inventory[i + 1].
// In either case, we will pick inventory[i - largestCount + 1..i].
const int pick = (i == inventory.size() - 1)
? inventory[i]
: inventory[i] - inventory[i + 1];
if (largestCount * pick >= orders) {
// We have run out of orders, so we need to recalculate the number of
// balls that we actually pick for inventory[i - largestCount + 1..i].
const int actualPick = orders / largestCount;
const int remaining = orders % largestCount;
return (ans +
largestCount *
trapezoid(inventory[i], inventory[i] - actualPick + 1) +
remaining * static_cast<long>(inventory[i] - actualPick)) %
kMod;
}
ans += largestCount * trapezoid(inventory[i], inventory[i] - pick + 1);
ans %= kMod;
orders -= largestCount * pick;
}
throw;
}
private:
long trapezoid(long a, long b) {
return (a + b) * (a - b + 1) / 2;
}
}; /* code provided by PROGIEZ */
1648. Sell Diminishing-Valued Colored Balls LeetCode Solution in Java
class Solution {
public int maxProfit(int[] inventory, int orders) {
final int kMod = 1_000_000_007;
long ans = 0;
long largestCount = 1;
Arrays.sort(inventory);
for (int i = inventory.length - 1; i >= 0; --i, ++largestCount)
if (i == 0 || inventory[i] > inventory[i - 1]) {
// If we are at the first inventory, or inventory[i] > inventory[i + 1].
// In either case, we will pick inventory[i..i + largestCount - 1].
final long pick = (i == 0) ? inventory[i] : inventory[i] - inventory[i - 1];
if (largestCount * pick >= orders) {
// We have run out of orders, so we need to recalculate the number of
// balls that we actually pick for inventory[i..i + largestCount - 1].
final long actualPick = orders / largestCount;
final long remaining = orders % largestCount;
return (int) ((ans +
largestCount * trapezoid(inventory[i], inventory[i] - actualPick + 1) +
remaining * (inventory[i] - actualPick)) %
kMod);
}
ans += largestCount * trapezoid(inventory[i], inventory[i] - pick + 1);
ans %= kMod;
orders -= largestCount * pick;
}
throw new IllegalArgumentException();
}
private long trapezoid(long a, long b) {
return (a + b) * (a - b + 1) / 2;
}
} // code provided by PROGIEZ
1648. Sell Diminishing-Valued Colored Balls LeetCode Solution in Python
class Solution:
def maxProfit(self, inventory: list[int], orders: int) -> int:
kMod = 1_000_000_007
ans = 0
largestCount = 1
def trapezoid(a: int, b: int) -> int:
return (a + b) * (a - b + 1) // 2
for a, b in itertools.pairwise(sorted(inventory, reverse=True) + [0]):
if a > b:
# If we are at the last inventory, or inventory[i] > inventory[i + 1].
# In either case, we will pick inventory[i - largestCount + 1..i].
pick = a - b
# We have run out of orders, so we need to recalculate the number of
# balls that we actually pick for inventory[i - largestCount + 1..i].
if largestCount * pick >= orders:
actualPick, remaining = divmod(orders, largestCount)
return (ans +
largestCount * trapezoid(a, a - actualPick + 1) +
remaining * (a - actualPick)) % kMod
ans += largestCount * trapezoid(a, a - pick + 1)
ans %= kMod
orders -= largestCount * pick
largestCount += 1 # code by PROGIEZ
