Maximum Ice Cream Bars

Problem:

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the ith ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.

Note: The boy can buy the ice cream bars in any order.

Return the maximum number of ice cream bars the boy can buy with coins coins.

You must solve the problem by counting sort.

Solution

In order for the boy to buy as many ice cream bars as possible, he needs to buy ice cream bars starting with the smallest price. So, we need to sort the cost array, then loop through it, keeping a count of the ice cream bars the boy is able to buy. You can either keep track of a sum of the cost of the ice cream bars until we are unable to add on more without surpassing coins, or alternatively, subtract the cost of each ice cream bar from coins until you can no longer subtract from it.

class Solution:  
    def maxIceCream(self, costs: List[int], coins: int) -> int:  
        sorted_costs = sorted(costs)  
        sum_costs = 0   
        i = 0   
        while i < len(sorted_costs) and sum_costs <= coins:  
            sum_costs += sorted_costs[i]  
            i += 1  
        if sum_costs > coins:   
            return i - 1  
        return i   

Runtime The time complexity is $O(n \log{}n)$, since we are sorting the list, and a space complexity of $O(n)$

Back to Greedy Algorithm Problems

---

anusha-murali.github.io