Maximum Ice Cream Bars

Introduction 

Greedy algorithms are simple instinctive algorithms that are used to solve optimization problems (either maximised or minimised). This algorithm chooses the best option at each step and seeks the best solution to the overall problem.

In this article, we will discuss an easy optimization problem by solving it using a greedy approach.

Problem Statement

Alice wants to buy some ice creams for him on a sweltering summer day. There are 'n' ice cream bars in the store. He has X number of coins, and he wants to buy the maximum ice cream bars from the store. We have to help him to purchase the ice cream bars.

We are given an array cost[] of length n, where the value of the ith element in the array is the number of coins required to purchase that ith ice cream, and n is the number of ice cream bars. Our task is to find the maximum number of ice creams he can buy with X coins.

Sample Test Cases

Example 1:

Input: cost[] = {2,4,1,5,2,1}, X=10
Output: 5
Explanation: Alice will buy the ice creams from the indices (0,1,2,4,5) for a total price of 2+4+1+2+1=10.

Example 2:

Input cost[] = {8, 1, 2, 5, 4, 3}, X=13
Output: 4
Explanation: Alice will buy the ice creams from the indices (1, 2, 4, 5) for a total price of 1+2+4+3 = 10. 

Approach

Alice wants to purchase the maximum ice cream bars with X coins. So the idea is straightforward, We will start purchasing the ice cream bars from the lowest to highest price till the sum of the coins required to purchase the ice cream bars does not exceed X.

To do this, we will sort the array in ascending order and start purchasing the bars one by one from the starting.

Steps:

• Declare an ans variable to store the count of maximum ice cream bars and initialise it with 0.
• Sort the cost array, sort(cost, cost+n).
• Traverse the array from the first element and subtract the current element's value from X.
• Now check, if the value of X is greater than or equal to 0, increment the ans variable by 1.
• Else break the loop and return the value of the ans.

Let’s understand the above approach with an example:

cost[] = {8, 1, 2, 5, 4, 3}, X=13

Steps:

• Sort the array, cost[] = {1, 2, 3, 4, 5, 8}
• Run a for loop from i=0 to i<n.
• i = 0, current element = 1, subtract the current element from X, X = 13-1 = 12, increment the ans by 1, ans = 1.
• i = 1, current element = 2, subtract the current element from X, X = 12-2 = 10, increment the ans by 1, ans = 2.
• i = 2, current element = 3, subtract the current element from X, X = 10-3 = 7, increment the ans by 1, ans = 3.
• i = 3, current element = 4, subtract the current element from X, X = 7-4 = 3, increment the ans by 1, ans = 4.
• i = 4, current element = 5, subtract the current element from X, X = 3-5 = -2.
• Now, the value of X<0, break the loop and return the ans.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
int max_ice_cream_bars(int cost[], int n, int X)
{
    int ans = 0;
    sort(cost, cost + n);
    for (int i = 0; i < n; i++)
    {
        X = X - cost[i];

        if (X < 0)
            break;
        else
            ans++;
    }
    return ans;
}
int main()
{
    int cost[] = {8, 1, 2, 5, 4, 3};
    int X = 13;
    int n = sizeof(cost) / sizeof(cost[0]);
    cout << max_ice_cream_bars(cost, n, X) << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

4

Complexity Analysis

Time complexity-  As we are sorting and traversing the whole array, the time complexity of the above solution is O(n*logn), where n is the size of the array.

Space complexity - The space complexity of the above solution is O(1).

Also Read - Selection Sort in C