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:

  1. Sort the given input list costs in ascending order.
  2. 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.

  1. After sorting the costs, we get [1,1,2,3,4].
  2. 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}