Maximum Ice Cream Bars

Problem Statement

On a hot summer day, a boy is at a store aiming to purchase some ice cream bars. He has a certain amount of coins, and his objective is to maximize the number of ice cream bars he can buy with these coins. The store has n different ice cream bars, each with a specific cost presented in an array costs of length n, where costs[i] represents the cost of the ith ice cream bar. The boy is free to purchase the ice cream bars in any order he prefers.

The task is to determine the maximum number of ice cream bars the boy can purchase without exceeding the amount of coins he possesses.

Examples

Example 1

Input:

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

Output:

4

Explanation:

The boy can buy ice cream bars at indices 0, 1, 2, and 4 for a total price of 1 + 3 + 2 + 1 = 7.

Example 2

Input:

costs = [10,6,8,7,7,8], coins = 5

Output:

0

Explanation:

The boy cannot afford any of the ice cream bars.

Example 3

Input:

costs = [1,6,3,1,2,5], coins = 20

Output:

6

Explanation:

The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.

Constraints

• costs.length == n
• 1 <= n <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= coins <= 10^8

Approach and Intuition

The problem revolves around maximizing the number of ice cream bars a boy can purchase with his available coins. Here's a structured approach leveraging the counting sort mechanism:

1. Sort the Costs: Sort the array costs in non-decreasing order to prioritize purchasing cheaper bars first.

2. Initialize Counters: Set up a counter for the number of ice cream bars purchased and a running total for the coins used.

3. Iterate Over Sorted Costs:

   • For each cost, check if the boy still has enough coins.
   • If yes, subtract the cost from coins and increment the counter.
   • If not, stop the iteration.

4. Return the Count: The counter now holds the maximum number of ice cream bars the boy can buy.

This greedy approach ensures optimal use of the budget by always choosing the cheapest remaining item, making it efficient and well-suited for the problem’s constraints.

Solutions

class Solution {
public:
    int maximumIceCream(vector<int>& prices, int budget) {
        int countPrices = prices.size();
        int maxPrice = *max_element(prices.begin(), prices.end());
        int totalIceCreams = 0;
    
        vector<int> priceFrequency(maxPrice + 1);
        for (auto& price : prices) {
            priceFrequency[price]++;
        }
    
        for (int price = 1; price <= maxPrice; ++price) {
            if (priceFrequency[price] == 0) continue;
            if (budget < price) break;
                
            int maxPossible = min(priceFrequency[price], budget / price);
            budget -= price * maxPossible;
            totalIceCreams += maxPossible;
        }
    
        return totalIceCreams;
    }
};