Sell Diminishing-Valued Colored Balls
Asked at Goldman Sachs
Problem
Sell Diminishing-Valued Colored Balls gives you counts of balls per color; selling a ball earns its color's current count, and the count then drops by one. Given orders total sales, maximize the revenue modulo 10^9 + 7. Greedily sell the most plentiful color, but do it in bulk with arithmetic series, because orders can be 10^9.
Asked At
| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
Greedy is optimal: each sale should take the color with the highest current value. A max-heap does that, but popping one ball at a time is O(orders log n) — too slow.
Key insight: sort counts in descending order. The top w colors will be sold down together from their value to the next distinct value, like peeling horizontal layers off a skyline.
Selling all top w colors from value hi down to (but not including) lo earns w * (lo+1 + ... + hi) and uses w * (hi - lo) orders.
When the remaining orders do not cover a full layer, sell full = orders // w complete levels from each of the w colors, then orders % w more balls at the next value.
Compute series sums with (a + b) * (b - a + 1) / 2 and apply the modulo carefully in fixed-width languages.
Optimal Approach
Step 1: Sort inventory descending and append 0.
Step 2: For i from 0 with width w = i + 1:
hi = inv[i], lo = inv[i+1]. If hi == lo, continue.
If w * (hi - lo) <= orders: add w * series(lo+1, hi); orders -= w * (hi - lo).
Else: full = orders // w, rem = orders % w; add w * series(hi-full+1, hi) + rem * (hi - full); stop.
Stop when orders == 0.
Step 3: Return the total mod 10^9 + 7.
Time: O(n log n). Space: O(1) extra.
What Trips People Up in Real Interviews
Simulating one sale at a time with a heap. orders can be 10^9.
Overflow in C++/Java: compute each series sum in 64-bit, reduce it mod 10^9 + 7, then multiply by the width.
Forgetting the partial layer: when orders run out mid-layer, some colors are sold one level deeper than others.
Not appending a 0 sentinel, which makes the last layer an edge case.
Solution Code
def maxProfit(inventory, orders):
MOD = 10**9 + 7
inv = sorted(inventory, reverse=True) + [0]
def series(a, b):
return (a + b) * (b - a + 1) // 2
total = 0
for i in range(len(inv) - 1):
w = i + 1
hi, lo = inv[i], inv[i + 1]
if hi == lo:
continue
if w * (hi - lo) <= orders:
total += w * series(lo + 1, hi)
orders -= w * (hi - lo)
else:
full, rem = divmod(orders, w)
total += w * series(hi - full + 1, hi) + rem * (hi - full)
orders = 0
if orders == 0:
break
return total % MODFrequently Asked Questions
What is the Sell Diminishing-Valued Colored Balls problem?
Sell Diminishing-Valued Colored Balls gives you counts of balls per color; selling a ball earns its color's current count, and the count then drops by one. Given `orders` total sales, maximize the revenue modulo `10^9 + 7`. Greedily sell the most plentiful color, but do it in bulk with arithmetic series, because `orders` can be `10^9`.
How do you solve Sell Diminishing-Valued Colored Balls?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Sell Diminishing-Valued Colored Balls?
Sell Diminishing-Valued Colored Balls is asked at Goldman Sachs. It is a medium difficulty problem.
What are common mistakes on Sell Diminishing-Valued Colored Balls?
- Simulating one sale at a time with a heap. `orders` can be `10^9`.
- Overflow in C++/Java: compute each series sum in 64-bit, reduce it mod `10^9 + 7`, then multiply by the width.
- Forgetting the partial layer: when orders run out mid-layer, some colors are sold one level deeper than others.
- Not appending a 0 sentinel, which makes the last layer an edge case.