Sponsored
Sponsored
This approach involves sorting the array of costs to ensure the boy buys the cheapest available ice cream bars first. After sorting, iterate through the list and keep buying bars until you run out of coins.
Steps involve:
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1), as no additional space is required beyond the input.
1#include <vector>
2#include <algorithm>
3#include <iostream>
4
5int maxIceCream(std::vector<int>& costs, int coins) {
6 std::sort(costs.begin(), costs.end());
7 int count = 0;
8 for (int cost : costs) {
9 if (coins >= cost) {
10 coins -= cost;
11 count++;
12 } else {
13 break;
14 }
15 }
16 return count;
17}
18
19int main() {
20 std::vector<int> costs = {1, 3, 2, 4, 1};
21 int coins = 7;
22 std::cout << maxIceCream(costs, coins) << std::endl;
23 return 0;
24}This C++ solution utilizes the STL sort function to sort the costs in non-descending order and then iterates over them to spend the coins efficiently, keeping track of the ice creams purchased in the count variable.
This solution uses a variation of counting sort suitable for this specific problem due to the constraint that costs[i] <= 100,000.
Steps involve:
Time Complexity: O(n + max(costs)), where max(costs) could be up to 100,000.
Space Complexity: O(max(costs)), because of the frequency array used.
1def maxIceCream(costs, coins):
2 max_cost = max(costs)
This Python solution uses a frequency array to store the number of each cost. By iterating over these costs in order (with known max cost), it calculates how many bars of each cost can be purchased and subtracts the respective cost from the available coins, tallying the total ice creams bought.