We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Ice Cream Bars

Number: 1961

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of ice cream bar costs and a total number of coins, determine the maximum number of ice cream bars the boy can buy. The bars can be purchased in any order, and the solution must use counting sort to efficiently process the costs.

Key Insights

  • Utilize counting sort since the cost values are within a known, limited range.
  • Instead of sorting the entire array, count the frequency of each cost.
  • Iterate over the costs starting from the smallest value, subtracting from the available coins and counting the number of bars that can be bought.
  • Stop once the coins are exhausted or there are no further affordable bars.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of ice cream bars and m is the maximum cost value (since we iterate over the frequency array up to m). Space Complexity: O(m), to store the frequency counts for costs from 1 up to the maximum cost.

Solution

We use counting sort by creating an array (or hashmap) to count how many ice cream bars exist for each possible cost. Then, traversing the cost values in increasing order, we subtract the cumulative cost from the coins available and add to the count of bars bought. This greedy approach ensures that we always buy the cheapest available ice cream bars first, maximizing the total number purchased.

Code Solutions

# Define the function to calculate maximum ice cream bars
def maxIceCream(costs, coins):
    # Determine the maximum cost to know the size of our counting array.
    max_cost = max(costs)
    # Create a count array for all cost values from 0 to max_cost. 
    # We use max_cost + 1 because costs are 1-indexed in value.
    count = [0] * (max_cost + 1)
    
    # Count the frequency of each cost
    for cost in costs:
        count[cost] += 1

    bars_bought = 0
    # Iterate over each possible cost from 1 to max_cost
    for cost in range(1, max_cost + 1):
        if count[cost] > 0:
            # Maximum bars we can buy at this cost without exceeding coins
            max_bars_at_cost = min(count[cost], coins // cost)
            bars_bought += max_bars_at_cost
            coins -= cost * max_bars_at_cost
            # If coins are exhausted, break out early
            if coins < cost:
                break
    return bars_bought

# Example usage:
print(maxIceCream([1,3,2,4,1], 7))  # Expected output: 4
← Back to All Questions