Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The price of a flower is its original cost times one plus the number of flowers that buyer has ALREADY purchased. To minimise the total, the most expensive flowers must be bought first (multiplier 1) and the cheap ones absorb the higher multipliers. Sort the costs descending; the i-th costliest flower (0-indexed) is bought at multiplier (i / k + 1) where k is the number of friends. O(n log n) from the sort.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you correctly model the price function (multiplier = previous purchases + 1) and then realise the optimal pairing is largest-cost-to-smallest-multiplier, distributed evenly across the k friends.
Where candidates slip
Sorting ascending (so cheap flowers get the low multipliers and expensive ones get inflated), or confusing k = friends with k = flowers.
How to stand out
State the rearrangement / exchange argument: if a cheaper flower were bought before a pricier one by the same friend, swapping them lowers the total, so costliest-first is optimal.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Sort descending, then round-robin the multiplier so the priciest flowers are bought first.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Try Every Order of Purchase
1Hint 1Explore hintHide hint
A solution is an assignment of each flower to a friend plus the order each friend buys their flowers. What does that determine for every flower?
2Hint 2Explore hintHide hint
Given any full ordering of all n purchases, the multiplier of a flower is fixed by how many that friend already bought. Try every permutation of the flowers and assign multipliers round-robin across friends.
3Hint 3Explore hintHide hint
Score each permutation and keep the minimum total. Correct, but n! permutations make it useless beyond tiny n — use it only to motivate sorting.
A · Core idea
Think of a candidate solution as an ordering of all n flowers. If we hand them out round-robin to the k friends in that order, the flower at position i (0-indexed) is bought at multiplier i / k + 1: the first k positions are each some friend's first purchase (×1), the next k are second purchases (×2), and so on.
Why permuting the flowers covers all cases. The multiset of multipliers is fixed once n and k are known — it's always k ones, then k twos, and so on. The only freedom we have is which cost receives which multiplier. Permuting the flowers and applying the positional multiplier i / k + 1 enumerates every possible pairing.
Why it's correct but hopeless. Every assignment is tried, so the minimum found is the true optimum. But there are n! permutations; even n = 12 is half a billion. The brute force exists only to make the structure visible.
The structure it reveals. Look at the multiplier sequence 1,1,…,2,2,…: it's non-decreasing with position. To minimise Σ multiplier(i) · cost(i), the rearrangement inequality says pair the smallest multipliers with the largest costs. That means: sort the costs descending and read off the positional multipliers. No search needed.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
k = 2, c = [2, 5, 6]order [2,5,6]
1·2 + 1·5 + 2·6 = 19
best = 1915 (achieved by putting the largest costs at the low multipliers)C · Code with teaching comments
Reference implementation previewpublic int getMinimumCost(int k, int[] c) { int[] best = { Integer.MAX_VALUE }; permute(c, 0, k, best); return best[0]; }Explore the full codeHide the full code
D · Why it works and complexityO(n! · n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The multipliers are a sorted (non-decreasing) sequence and we just choose how to pair them with costs. Minimising a sum of paired products with one sequence fixed is exactly the rearrangement inequality — oppositely sort the two sequences.
ComplexityO(n! · n) time, O(n) space — There are n! orderings of the flowers; scoring each costs O(n). No structure is exploited, so the factorial dominates.
E · Edge cases and pitfalls3Factorial blow-up — only feasible for n ≤ ~10; it's a teaching device, not a submission.Explore edge casesHide edge cases
Pitfalls
- Factorial blow-up — only feasible for n ≤ ~10; it's a teaching device, not a submission.
- Forgetting the multiplier is positional under round-robin, not arbitrary.
- Minimising the wrong quantity (e.g. number of friends used) instead of total cost.
Approach 2 of 2 · Optimal
Greedy — Sort Descending, Round-Robin the Multiplier (Optimal)
1Hint 1Explore hintHide hint
The multipliers you'll pay are fixed: k flowers at 1×, the next k at 2×, and so on. You only choose which cost takes which multiplier. Which cost should get the smallest multiplier?
2Hint 2Explore hintHide hint
Put the biggest costs where the multiplier is smallest. Sort the costs descending so the priciest flower sits at position 0 (multiplier 1).
3Hint 3Explore hintHide hint
Sweep the sorted-descending array; the flower at index i pays multiplier i / k + 1. Sum (i / k + 1) · c[i]. One pass after the sort.
A · Core idea
Sort the costs in descending order. Walk the sorted array; the flower at index i (0-indexed) is the (i / k + 1)-th flower bought by whichever friend handles it under an even round-robin, so it costs (i / k + 1) · c[i]. Sum those products.
Why costliest-first — the exchange argument. Suppose an optimal plan buys a cheaper flower with cost a at a lower multiplier p while a pricier flower with cost b > a is bought at a higher multiplier q > p (by anyone). Their combined contribution is p·a + q·b. Swap the two flowers' purchase slots: now b takes multiplier p and a takes q, contributing p·b + q·a. The change is (p·b + q·a) − (p·a + q·b) = (q − p)(a − b) < 0 because q > p and a < b. The swap strictly lowers the total, so no optimal plan can put a smaller cost at a smaller multiplier than a larger cost. Hence the largest costs must take the smallest multipliers — exactly what sorting descending achieves.
Why the multiplier is `i / k + 1`. Spreading purchases as evenly as possible across k friends means the first k flowers are each some friend's first purchase (×1), the next k are second purchases (×2), and so on. Integer-dividing the 0-based index by k and adding 1 reproduces this 1,1,…,2,2,… staircase. An uneven distribution would only push some flower to a higher multiplier than necessary, never lower, so even round-robin is optimal.
Why k = friends matters. k is the count of buyers, so it's the width of each multiplier 'band'. With more friends the bands are wider, more flowers stay at multiplier 1, and the total drops. Confusing k with n breaks the band width.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
k = 3, c = [1, 3, 5, 7, 9]Array state
i=0 (9)
mult 1 → +9
29C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
This is the rearrangement inequality in disguise: with the multiplier sequence fixed and non-decreasing, the minimum weighted sum pairs it oppositely with the costs. Sort costs descending against an ascending multiplier staircase. 'One sequence is forced, sort the other the opposite way' is the reusable kernel.
ComplexityO(n log n) time, O(1) space — Sorting the costs is O(n log n) and dominates; the weighted-sum sweep is O(n) with only scalar accumulators → O(1) extra space.
E · Edge cases and pitfalls6k = n (friends = flowers) — Every index i < k, so i/k = 0 and every flower pays multiplier 1 — total is just the plain sum.Explore edge casesHide edge cases
Edge cases handled
k = n (friends = flowers)Every index i < k, so i/k = 0 and every flower pays multiplier 1 — total is just the plain sum.k = 1 (one friend)Multiplier is i + 1; the single friend buys all flowers, paying 1×,2×,3×,… on the descending order.n = 1One flower at multiplier 1 → total = c[0] regardless of k.
Pitfalls
- Sorting ascending — cheap flowers grab the low multipliers and expensive ones get inflated, maximising instead of minimising.
- Using n instead of k as the band width — wrong multipliers throughout.
- Off-by-one on the multiplier — it's i/k + 1, not i/k (the first purchase is 1×, never 0×).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int getMinimumCost(int k, int[] c) { Integer[] flowers = new Integer[c.length]; for (int i = 0; i < c.length; i++) { flowers[i] = c[i]; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Sorting ascending instead of descending
The largest costs must receive the smallest multipliers. Ascending order does the opposite, inflating the total.
Explore the code comparisonHide the code comparison
Sorting ascending instead of descending
The largest costs must receive the smallest multipliers. Ascending order does the opposite, inflating the total.
Don't write this
c.sort()
total = sum((i // k + 1) * cost for i, cost in enumerate(c))Write this instead
c.sort(reverse=True)
total = sum((i // k + 1) * cost for i, cost in enumerate(c))2Off-by-one in the multiplier
A friend's first purchase costs 1×, not 0×. The multiplier is i/k + 1; dropping the +1 makes the first band free.
Explore the code comparisonHide the code comparison
Off-by-one in the multiplier
A friend's first purchase costs 1×, not 0×. The multiplier is i/k + 1; dropping the +1 makes the first band free.
Don't write this
int multiplier = i / k;
total += multiplier * flowers[i];Write this instead
int multiplier = i / k + 1;
total += multiplier * flowers[i];3Treating k as the flower count
k is the number of friends and sets the band width. Using n splits everyone into their own band and breaks the round-robin.
Explore the code comparisonHide the code comparison
Treating k as the flower count
k is the number of friends and sets the band width. Using n splits everyone into their own band and breaks the round-robin.
Don't write this
n = len(c)
total = sum((i // n + 1) * cost for i, cost in enumerate(c))Write this instead
total = sum((i // k + 1) * cost for i, cost in enumerate(c))Revise
Carry the pattern into the interview
Pattern to remember
Greedy: assign the smallest multipliers to the largest costs (sort descending, round-robin the multiplier)
Code pattern to memorize
sort c descending
total = 0
for i, cost in enumerate(c):
total += (i // k + 1) * cost # k = number of friends
return totalRules to remember
- 1A flower's price =
(previous purchases by that friend + 1) * originalCost. The +1 means the first flower a friend buys costs full price. - 2Spread purchases evenly across the k friends: with the costs sorted descending, the i-th flower (0-indexed) gets multiplier
i / k + 1. - 3Buy expensive flowers first so they get the lowest multiplier — the exchange argument proves this is optimal.
- 4
kis the number of friends (buyers), not the number of flowers. Misreading this swaps the multiplier formula. - 5Integer division
i / kin Java is floor division — exactly what the round-robin needs; mirror it withi // kin Python.
Use this pattern when
- A per-item cost is scaled by a multiplier that grows with how many items the same actor has already taken
- You can distribute items across several actors to keep multipliers low
- Minimising a sum of (weight × multiplier) where you control which weight gets which multiplier
- The multipliers form a fixed multiset and you only choose the pairing
Choose another pattern when
- The multiplier depends on the VALUE bought, not just the count → greedy pairing breaks
- Buyers have individual budgets or limits → constrained assignment, not a clean sort
- Items interact (buying one changes another's cost) → DP or flow
- You must minimise the number of buyers under a price cap → different objective entirely
Interview takeaway
When you pair a fixed set of multipliers with a set of weights to minimise the weighted sum, the rearrangement inequality says: pair the largest weight with the smallest multiplier. Sort descending and round-robin the multipliers — the same move appears in any 'assign costs to growing prices' problem.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternRearrangement-inequality greedy: a fixed, sorted multiplier sequence is paired with item weights to minimise a weighted sum. Sort the weights opposite to the multipliers (descending against an ascending staircase). The same kernel drives any 'assign growing prices to costs' problem.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Mark and ToysAnother sort-and-sweep greedy — maximise the count of items under a budget.
- Luck BalanceSort by magnitude and spend a capped budget of favourable choices on the largest items.
- Minimum Cost to Connect SticksRepeated weighted sums minimised with a heap rather than a single sort.
- Task SchedulerComing soonGreedy assignment of high-frequency items first to minimise idle multipliers.