algoadvance

You are given an integer array cost where cost[i] is the cost of the i-th candy.

Return the minimum cost of buying all the candies. In order to get the discount, you will follow these steps:

  1. Pick the 2 most expensive candies.
  2. Out of those 2 picked candies, pay the cost of the most expensive candy and get the other candy for free.
  3. Repeat this process until all candies are consumed.

Clarifying Questions

  1. Are the candy costs in the array always positive integers?
    • Yes, you can assume each candy has a positive integer cost.
  2. What if the number of candies is odd?
    • If there’s an odd number of candies, the last remaining candy will be paid for at full price.
  3. Are there any constraints on the size of the array?
    • Yes, the size of the array could be large, so the solution should be efficient.

Strategy

To minimize the total cost:

  1. Sort the cost array in descending order.
  2. Process the sorted array in chunks of three candies each. In each chunk, you pay for the two most expensive candies, and the third candy (which is the cheapest in the chunk) is free.
  3. Sum up the costs of the paid candies.

Code

Here’s a Python code solution that follows the above strategy:

def minimumCost(cost):
    # Sort the list in descending order
    cost.sort(reverse=True)
    
    total_cost = 0
    n = len(cost)
    
    # Process the candies in chunks of three
    for i in range(n):
        # Add the cost of the candy if it's not the third one in a group of three
        if i % 3 != 2:
            total_cost += cost[i]
    
    return total_cost

# Example usage:
print(minimumCost([1, 2, 3]))  # Output: 5
print(minimumCost([6, 5, 7, 9, 2, 2]))  # Output: 23
print(minimumCost([5, 5]))  # Output: 10

Time Complexity

Hence, the overall time complexity is (O(n \log n)) due to the sorting step.

This approach ensures that we are minimizing the cost by taking the optimal discount repeatedly.

Try our interview co-pilot at AlgoAdvance.com