Minimum Cost of Buying Candies With Discount
Easy
A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free. The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought. For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.
Given a 0-indexed integer array cost, where cost[i] denotes the cost of the i<sup>th</sup> candy, return the minimum cost of buying all the candies.
Example 1:
Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free. The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
Example 2:
Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.
Write a function to efficiently determine the minimum cost to buy all candies.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the constraints on the size of the `cost` array, and the range of values within it?
- Can the `cost` values be zero or negative?
- If the number of candies is not a multiple of 3, how should the remaining candies be handled after applying the discount?
- Is the goal to minimize the *total* cost, or is there another metric I should be optimizing for?
- If multiple purchase strategies result in the same minimum cost, is any one acceptable, or is there a preferred strategy?
Brute Force Solution
Approach
The brute force approach involves checking every possible combination of candy purchases to find the one with the minimum cost. This is done by exploring all possible buying strategies, considering the discount rule for each strategy, and then picking the cheapest.
Here's how the algorithm would work step-by-step:
- Consider all the ways you can buy candies.
- For each way of buying candies, sort the prices from highest to lowest.
- Apply the discount rule. For every 'k' candies you buy, the cheapest one is free. Calculate the total cost after applying the discount.
- Keep track of the cost for each way you tried to buy the candies.
- Compare all the costs you've calculated.
- The smallest cost is the minimum cost you're looking for.
Code Implementation
def minimum_cost_brute_force(candies, k):
number_of_candies = len(candies)
minimum_total_cost = float('inf')
# Iterate through all possible combinations of buying candies
for i in range(1 << number_of_candies):
bought_candies = []
for j in range(number_of_candies):
if (i >> j) & 1:
bought_candies.append(candies[j])
number_of_bought_candies = len(bought_candies)
# Sort the prices of the bought candies from highest to lowest.
bought_candies.sort(reverse=True)
current_total_cost = 0
free_candies = number_of_bought_candies // (k + 1)
# Apply the discount rule and calculate total cost
for index in range(number_of_bought_candies):
if (index + 1) > number_of_bought_candies - free_candies:
current_total_cost += bought_candies[index]
# Update the minimum cost if the current cost is lower.
minimum_total_cost = min(minimum_total_cost, current_total_cost)
return minimum_total_costBig(O) Analysis
Optimal Solution
Approach
To minimize the cost, we want to take advantage of the 'buy two, get one free' deal as much as possible. The best way to do this is to buy the most expensive candies and get the cheapest ones for free.
Here's how the algorithm would work step-by-step:
- First, sort the candy prices from highest to lowest.
- Then, for every three candies, buy the two most expensive ones, and get the cheapest of the three for free.
- Continue this process until all candies have been considered.
- Finally, add up the prices of all the candies you bought. This is the minimum cost.
Code Implementation
def minimum_cost_of_buying_candies(candy_prices, free_candies):
candy_prices.sort(reverse=True)
number_of_candies = len(candy_prices)
minimum_cost = 0
# Iterate through candies, buying 2 and getting 1 free
for i in range(0, number_of_candies, free_candies + 1):
# Add the cost of the candies we are buying
for j in range(min(free_candies + 1, number_of_candies - i) - (free_candies // (free_candies+1)) , min(free_candies + 1, number_of_candies - i)):
minimum_cost += candy_prices[i + j]
return minimum_costBig(O) Analysis
Edge Cases
| Case | How to Handle |
|---|---|
| Empty costs array | Return 0 if the costs array is empty as there are no candies to buy. |
| Null costs array | Throw an IllegalArgumentException or return -1 to indicate an invalid input. |
| Single element costs array | Return the cost of that single candy since no discount applies. |
| Costs array with negative values | Throw an IllegalArgumentException as candy costs cannot be negative. |
| Costs array with zero values | The algorithm should handle zero costs correctly without causing errors. |
| Costs array with duplicate values | Sorting and applying the discount will correctly handle duplicate cost values. |
| Large costs array (scalability) | Sorting with an efficient algorithm like merge sort or quicksort will ensure O(n log n) time complexity. |
| Integer overflow on sum of costs | Use long data type to store the total cost to prevent potential overflow issues with very large cost values. |
