Minimum Cost of Buying Candies With Discount

Easy

Minimum Cost of Buying Candies With Discount

Easy

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_cost

Big(O) Analysis

Time Complexity

O(n!) – The described approach involves considering all possible combinations of buying candies. Generating all combinations for n candies results in n! (n factorial) possibilities. For each combination, sorting the prices takes O(n log n) time. Calculating the cost after applying the discount also takes O(n) time. Therefore, the overall time complexity is dominated by generating all combinations, leading to O(n!).

Space Complexity

O(N!) – The brute force approach explores all possible combinations of buying candies. The number of combinations can grow factorially with the number of candies, N. The algorithm keeps track of the cost for each combination tried, and to generate those combinations, it may use recursive calls or other mechanisms that implicitly or explicitly stores the current combination being evaluated. In the worst case, auxiliary space would be needed to hold all possible combinations which is proportional to N!. Thus, the auxiliary space complexity is O(N!).

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_cost

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this approach is sorting the candy prices. Sorting n elements using an efficient algorithm like merge sort or heap sort takes O(n log n) time. The subsequent iteration through the sorted array to calculate the cost involves a single pass through the n elements, which takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The algorithm sorts the input list in-place. Beyond the input list itself, no additional data structures like arrays, hash maps, or trees are created. It only uses a few constant space variables to iterate through the sorted list and calculate the cost. Therefore, the auxiliary space complexity is constant, independent of the number of candies, N.

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.