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

Minimum Cost of Buying Candies With Discount

Number: 2248

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array cost where cost[i] represents the cost of the ith candy, a discount is offered: for every two candies purchased, you can get a third candy for free. The free candy must have a cost that is less than or equal to the minimum cost of the two candies you purchase. The task is to determine the minimum total cost required to buy all the candies.

Key Insights

  • Sorting the candies in descending order allows for a valid grouping where the cheapest candy in each group (the free one) satisfies the discount condition.
  • For every group of three candies, paying for the two most expensive candies minimizes the overall cost.
  • Iterating over the sorted array and summing only the candies at positions not equal to 2 mod 3 ensures that you correctly skip the free candy in each group.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(log n) if the sorting algorithm is in-place (or O(n) in the worst-case scenario).

Solution

The solution begins by sorting the candy costs in descending order. This way, when you group every three candies, the smallest candy in each group (which is the free candy) is always eligible because its cost is less than or equal to the other two candies in that group. By iterating through the sorted list and summing the cost of every candy except the third one (i.e., those where the index modulo 3 equals 2), you get the minimum total cost to purchase all candies.

Code Solutions

# Python solution

def minimumCost(cost):
    # Sort the candy costs in descending order
    cost.sort(reverse=True)
    total_cost = 0
    # Iterate through the candies and sum the cost skipping every third candy (free candy)
    for i in range(len(cost)):
        if i % 3 != 2:
            total_cost += cost[i]
    return total_cost

# Example test
print(minimumCost([6,5,7,9,2,2]))  # Expected output: 23
← Back to All Questions