1067. Ice Cream Budget
On a hot afternoon a kiosk displays its bars, and costs[i] is the price in coins of bar i. You start with coins coins and may buy the bars in any order, but each bar can be bought at most once. Return the largest number of bars you can afford in total.
Prices are bounded by 100000, which allows ordering them without a comparison sort: tally how many bars cost each price and then walk the prices upward from the cheapest, buying as many of each price as the remaining coins allow. This runs in O(n + maxCost) time and O(maxCost) extra space.
Example 1
- Input:
- costs = [5,2,9,2,7], coins = 11
- Output:
- 3
- Explanation:
Buying the cheapest bars costing 2, 2 and 5 uses 9 coins; adding the 7 would exceed 11, so 3 bars.
Example 2
- Input:
- costs = [4,4,4], coins = 3
- Output:
- 0
- Explanation:
Every bar costs more than the 3 coins available, so nothing can be bought.
Example 3
- Input:
- costs = [6,1,3,2,8], coins = 7
- Output:
- 3
- Explanation:
The three cheapest bars cost 1, 2 and 3 for 6 coins, and the next cheapest costs 6, which does not fit in the remaining coin.
Constraints
1 ≤ costs.length ≤ 105
1 ≤ costs[i] ≤ 105
1 ≤ coins ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n + maxCost)
- Space
- O(maxCost)