Maximum Ice Cream Bars
Problem
You are given an array costs, where costs[i] is the price of the i-th ice cream bar, and an integer coins holding the money you have. Buy as many bars as possible — each bar can be bought at most once — and return the maximum number of bars you can afford.
costs = [1, 3, 2, 4, 1], coins = 74def max_ice_cream(costs, coins):
costs.sort()
bought = 0
for price in costs:
if price > coins:
break
coins -= price
bought += 1
return boughtfunction maxIceCream(costs, coins) {
costs.sort((a, b) => a - b);
let bought = 0;
for (const price of costs) {
if (price > coins) break;
coins -= price;
bought += 1;
}
return bought;
}class Solution {
public int maxIceCream(int[] costs, int coins) {
Arrays.sort(costs);
int bought = 0;
for (int price : costs) {
if (price > coins) break;
coins -= price;
bought += 1;
}
return bought;
}
}int maxIceCream(vector<int>& costs, int coins) {
sort(costs.begin(), costs.end());
int bought = 0;
for (int price : costs) {
if (price > coins) break;
coins -= price;
bought += 1;
}
return bought;
}Explanation
We want the most bars for a fixed amount of money. Every bar counts the same toward the total — one bar is one bar — so the only thing that matters per bar is how much it drains from our coins.
That points straight at a greedy idea: spend on the cheapest bar still available first. A cheap bar leaves more coins for later, and it can never be worse than buying a pricier bar in its place, because both add the same +1 to the count.
So we sort the prices ascending, then walk left to right paying for each bar in turn. As soon as we hit a price we cannot afford, every remaining price is at least that large, so we stop — nothing further is reachable.
Example: costs = [1, 3, 2, 4, 1], coins = 7. Sorted it becomes [1, 1, 2, 3, 4]. Pay 1 (6 left), 1 (5 left), 2 (3 left), 3 (0 left) — that is 4 bars. The next price is 4 but we have 0 coins, so we stop with the answer 4.
Because we sorted once and then made a single pass, the work is dominated by the sort.