1833. Maximum Ice Cream Bars

Time: O(n log n)

Space: O(1)

Problem Overview

Buy as many ice cream bars as possible with a fixed coin budget.

Intuition

Buy as many ice cream bars as possible with a fixed coin budget. Each bar has a cost — always take the cheapest available bars first. Sort costs ascending, subtract each cost from coins while you can afford it, and stop at the first bar that exceeds the remaining coins. The index where you stop is the count of bars bought.

Algorithm

1Sort costs in ascending order.
2Loop i from 0 to n − 1: if coins >= costs[i], subtract costs[i]; else return i.
3If the loop finishes, return costs.Length (afforded all bars).

Example Walkthrough

Input: costs = [1,3,2,4,1], coins = 7

1.Sorted costs → [1, 1, 2, 3, 4].
2.Buy at 1 → coins = 6 (count 1).
3.Buy at 1 → coins = 5 (count 2).
4.Buy at 2 → coins = 3 (count 3).
5.Buy at 3 → coins = 0 (count 4).
6.Cannot afford 4 → return 4.

Output: 4

Common Pitfalls

•Sort first — greedy on unsorted costs is wrong.
•Return the index i when you cannot afford costs[i], not i − 1.
•If all bars fit, return costs.Length, not costs.Length − 1.

1833.cs

// Approach: Sort ice cream costs ascending and buy from cheapest first until coins run out.
// Count how many bars you can afford with a greedy scan after sorting.
// Time: O(n log n) Space: O(1) or O(log n) for sort
public class Solution
{
    public int MaxIceCream(int[] costs, int coins)
    {
        Array.Sort(costs);

        for (int i = 0; i < costs.Length; ++i)
        {
            if (coins >= costs[i])
                coins -= costs[i];
            else
                return i;
        }

        return costs.Length;
    }
}

Was this solution helpful?