Maximum Ice Cream Bars - Practice Coding Problems

Maximum Ice Cream Bars - Problem

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 ith 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.

You must solve the problem by counting sort.

Input & Output

Example 1 — Basic Case

$ Input: costs = [1,3,2,4,1], coins = 7

› Output: 4

💡 Note: Buy ice cream bars at costs [1,1,2,3] for total cost 7. Cannot afford the bar costing 4, so maximum count is 4.

Example 2 — Exact Budget

$ Input: costs = [10,6,8,7,7,8], coins = 5

› Output: 0

💡 Note: All ice cream bars cost more than 5 coins, so we cannot buy any. Return 0.

Example 3 — All Affordable

$ Input: costs = [1,6,3,1,2,5], coins = 20

› Output: 6

💡 Note: We can afford all ice cream bars: 1+1+2+3+5+6 = 18 ≤ 20. Buy all 6 bars.

Constraints

1 ≤ costs.length ≤ 10⁵
1 ≤ costs[i] ≤ 10⁵
1 ≤ coins ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Array of ice cream costs and available coins

Sort & Select

Sort costs and buy cheapest items first

Output

Maximum number of ice cream bars purchased

Key Takeaway

🎯 Key Insight: Greedy approach works because buying cheaper items first always maximizes the total count within budget

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is to use greedy strategy: always buy the cheapest available ice cream first. Since the problem requires counting sort, we create a frequency array to sort costs in O(n) time, then greedily purchase from lowest to highest cost. Best approach is counting sort with Time: O(n + k), Space: O(k) where k is the cost range.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ)	O(n)	Generate all possible combinations of ice cream bars and find maximum count within budget
Sort First - Greedy Approach	O(n log n)	O(1)	Sort costs and greedily buy cheapest ice cream bars until budget runs out
Counting Sort - Required Solution	O(n + k)	O(k)	Use counting sort to sort prices in O(n) time, then greedily buy cheapest items

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible subsets of ice cream bars
For each subset, calculate total cost
If cost ≤ coins, update maximum count

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^n possible combinations

Check Budget

Calculate cost for each combination

Find Maximum

Return largest valid count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* costs, int costsSize, int coins) {
    int maxCount = 0;
    
    // Try all 2^n combinations
    for (int mask = 0; mask < (1 << costsSize); mask++) {
        int totalCost = 0;
        int count = 0;
        
        for (int i = 0; i < costsSize; i++) {
            if (mask & (1 << i)) {
                totalCost += costs[i];
                count++;
            }
        }
        
        if (totalCost <= coins) {
            if (count > maxCount) {
                maxCount = count;
            }
        }
    }
    
    return maxCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int costs[1000];
    int costsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        costs[costsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int coins;
    scanf("%d", &coins);
    
    int result = solution(costs, costsSize, coins);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

We generate 2^n subsets and check each one

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth for generating combinations

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler