Problem Description
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 i-th 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.
Key Insights
- The boy can buy ice cream bars in any order, so prioritizing cheaper bars will maximize the total count.
- Using counting sort allows us to efficiently handle the range of costs without needing to sort the entire array.
- We need to iterate through the possible costs and sum them until we exhaust the available coins.
Space and Time Complexity
Time Complexity: O(n + k), where n is the number of ice cream bars and k is the maximum cost of an ice cream bar.
Space Complexity: O(k), where k is the maximum cost of an ice cream bar, for the counting sort array.
Solution
To solve the problem, we will use a counting sort approach. First, we will create a count array to keep track of the number of ice cream bars at each possible cost. Then, we will iterate over the count array and accumulate the costs of the ice cream bars in ascending order, counting how many can be bought until the coins run out. This method is efficient and ensures we maximize the number of bars purchased.