algoadvance

Leetcode 2144. Minimum Cost of Buying Candies With Discount

Problem Statement

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 with a special discount applied: Every time you buy two candies, you get an additional candy for free, but you must pick the least expensive available candy as the free one.

Clarifying Questions

  1. What is the minimum number of candies you need to buy?
    • There is no minimum, you can buy all candies, one at a time if you want, but using the discount optimally minimizes the cost.
  2. Does “every time you buy two candies” mean that after buying any two, you can immediately get a free one?
    • Yes. Whenever you buy two candies, you can get one more for free, and repeat this process as many times as possible.
  3. What if there are fewer than three candies?
    • If there are fewer than three candies, just buy them all, as no discount can effectively apply.
  4. Can the array of cost be empty?
    • No, the problem ensures that there is at least one candy available.
  5. Is the “free” candy the cheapest among all the candies available or just the cheapest among the ones we are processing at that moment?
    • It’s the cheapest among all the candies available at that moment.

Strategy

To minimize the cost, sort the array in descending order, and always pick the third candy directly as free after every two candies bought. This ensures that we are optimizing the discount usage by giving away the least expensive candies.

Steps:

  1. Sort the cost array in descending order.
  2. Initialize total_cost to 0.
  3. Traverse through the list in steps of 3:
    • For every three candies, add the first and second candies’ cost to total_cost.
    • Skip the third candy as it is free.
  4. If any candies remain after fully processing groups of three, ensure to add their cost to the total_cost.

Code

Here is the implementation based on the described approach:

#include <iostream>
#include <vector>
#include <algorithm>

int minimumCost(std::vector<int>& cost) {
    // Sort the cost in descending order
    std::sort(cost.begin(), cost.end(), std::greater<int>());
    
    int totalCost = 0;
    
    // Traverse through the list in steps of 3
    for (size_t i = 0; i < cost.size(); i++) {
        // Add the cost of the first and second candies
        if (i % 3 != 2) {
            totalCost += cost[i];
        }
        // Skip the third candy (i.e., do nothing)
    }
    
    return totalCost;
}

// For testing purposes
int main() {
    std::vector<int> cost = {6, 5, 7, 9, 2, 2};
    std::cout << "Minimum cost: " << minimumCost(cost) << std::endl;
    return 0;
}

Time Complexity

Overall, the time complexity is dominated by the sorting step, hence O(n log n).

This solution is efficient and ensures that we apply the discount rule optimally to minimize the total cost.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI