Leetcode 1833. Maximum Ice Cream Bars Solution
Problem Explanation
The problem is about a boy who wants to buy ice cream bars from a store. There are n
ice cream bars with different costs, and the boy has a certain amount of coins to spend. The problem is asking us to find the maximum number of ice cream bars the boy can buy with the given amount of coins.
Example Walkthrough
Let's walk through the first example given in the problem description.
costs = [1,3,2,4,1]
and coins = 7
.
There are total 5 ice cream bars with prices [1,3,2,4,1]
, and the boy has 7 coins to spend. Our task is to find the maximum number of ice cream bars the boy can buy.
Solution Approach
A greedy approach will be used in this problem. The boy can buy the least expensive ice cream bars first to maximize the number of ice cream bars purchased.
The steps we will follow to solve this problem are:
- Sort the given input list
costs
in ascending order. - Iterate through the sorted list
costs
: a. If the boy has enough coins to buy the current ice cream bar, subtract the cost of the current ice cream bar from his total coins. b. If he cannot buy the current ice cream bar, return the count of how many ice cream bars were bought so far.
Example Execution
Using Example 1:
costs = [1,3,2,4,1]
and coins = 7
.
- After sorting the
costs
, we get[1,1,2,3,4]
. - Iterating through the sorted list:
a. The boy can buy the first ice cream bar with 1 coin. Remaining coins:
7-1=6
. b. The boy can buy the second ice cream bar with 1 coin. Remaining coins:6-1=5
. c. The boy can buy the third ice cream bar with 2 coins. Remaining coins:5-2=3
. d. The boy can buy the fourth ice cream bar with 3 coins. Remaining coins:3-3=0
. e. The boy cannot buy the fifth ice cream bar. So, return the count of ice cream bars bought, which is 4 in this case.
Python Solution
1from typing import List
2
3class Solution:
4 def maxIceCream(self, costs: List[int], coins: int) -> int:
5 costs.sort()
6 count = 0
7
8 for cost in costs:
9 if coins >= cost:
10 coins -= cost
11 count += 1
12 else:
13 return count
14
15 return count
Java Solution
1import java.util.Arrays;
2
3class Solution {
4 public int maxIceCream(int[] costs, int coins) {
5 Arrays.sort(costs);
6 int count = 0;
7
8 for (int cost : costs) {
9 if (coins >= cost) {
10 coins -= cost;
11 count++;
12 } else {
13 return count;
14 }
15 }
16
17 return count;
18 }
19}
JavaScript Solution
1class Solution {
2 maxIceCream(costs, coins) {
3 costs.sort((a, b) => a - b);
4 let count = 0;
5
6 for (let cost of costs) {
7 if (coins >= cost) {
8 coins -= cost;
9 count++;
10 } else {
11 return count;
12 }
13 }
14
15 return count;
16 }
17}
C++ Solution
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 int maxIceCream(std::vector<int>& costs, int coins) {
7 std::sort(costs.begin(), costs.end());
8 int count = 0;
9
10 for (int cost : costs) {
11 if (coins >= cost) {
12 coins -= cost;
13 count++;
14 } else {
15 return count;
16 }
17 }
18
19 return count;
20 }
21};
C# Solution
1using System;
2
3public class Solution {
4 public int MaxIceCream(int[] costs, int coins) {
5 Array.Sort(costs);
6 int count = 0;
7
8 foreach (int cost in costs) {
9 if (coins >= cost) {
10 coins -= cost;
11 count++;
12 } else {
13 return count;
14 }
15 }
16
17 return count;
18 }
19}
20```**Ruby Solution**
21
22```ruby
23class Solution
24 def max_ice_cream(costs, coins)
25 costs.sort!
26 count = 0
27
28 costs.each do |cost|
29 if coins >= cost
30 coins -= cost
31 count += 1
32 else
33 return count
34 end
35 end
36
37 return count
38 end
39end
Golang Solution
1import "sort"
2
3func maxIceCream(costs []int, coins int) int {
4 sort.Ints(costs)
5 count := 0
6
7 for _, cost := range costs {
8 if coins >= cost {
9 coins -= cost
10 count++
11 } else {
12 return count
13 }
14 }
15
16 return count
17}
Kotlin Solution
1import java.util.Arrays
2
3class Solution {
4 fun maxIceCream(costs: IntArray, coins: Int): Int {
5 Arrays.sort(costs)
6 var count = 0
7 var remainingCoins = coins
8
9 for (cost in costs) {
10 if (remainingCoins >= cost) {
11 remainingCoins -= cost
12 count++
13 } else {
14 return count
15 }
16 }
17
18 return count
19 }
20}
Swift Solution
1class Solution {
2 func maxIceCream(_ costs: [Int], _ coins: Int) -> Int {
3 let sortedCosts = costs.sorted()
4 var count = 0
5 var remainingCoins = coins
6
7 for cost in sortedCosts {
8 if remainingCoins >= cost {
9 remainingCoins -= cost
10 count += 1
11 } else {
12 return count
13 }
14 }
15
16 return count
17 }
18}
PHP Solution
1class Solution {
2 function maxIceCream($costs, $coins) {
3 sort($costs);
4 $count = 0;
5
6 foreach ($costs as $cost) {
7 if ($coins >= $cost) {
8 $coins -= $cost;
9 $count++;
10 } else {
11 return $count;
12 }
13 }
14
15 return $count;
16 }
17}
Scala Solution
1object Solution {
2 def maxIceCream(costs: Array[Int], coins: Int): Int = {
3 val sortedCosts = costs.sorted
4 var count = 0
5 var remainingCoins = coins
6
7 for (cost <- sortedCosts) {
8 if (remainingCoins >= cost) {
9 remainingCoins -= cost
10 count += 1
11 } else {
12 return count
13 }
14 }
15
16 return count
17 }
18}