Buy All Items Under a Two-Paid One-Free Offer
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
A shop lets you take one candy free for every two candies you pay for, provided the free candy costs no more than either paid candy. Given the price of every candy in `cost`, return the minimum payment needed to obtain them all. Each candy belongs to at most one paid-pair/free-candy group, and candies not taken free must be paid for.
```cpp
class Solution {
public:
int minimumCost(vector<int>& cost);
};
```
### Examples
**Example 1:**
```text
cost = [8,6,4,2]
Output: 16
Explanation: Pay 8 and 6 to get 4 free, then pay 2.
```
**Example 2:**
```text
cost = [3,3,3]
Output: 6
Explanation: Pay for two equal-priced candies and take the third free.
```
### Constraints
- `1 <= cost.length <= 100`.
- `1 <= cost[i] <= 100`.
### Clarifying Questions
One or two leftover candies must be paid for. A free candy cannot sponsor another free candy.
```hint Inspect the structure
In descending price order, what is the most expensive possible first free item?
```
### Reasoning checkpoints
- Respect the price limit on every free candy and never reuse a paid candy to support several discounts.
- Account for all candies, including one or two left outside complete discount groups.
- Justify the minimum total payment when prices tie as well as when they differ.
### Optional extensions
How would the rule change for three paid candies and a fourth free?
Overview: Buy All Items Under a Two-Paid One-Free Offer. For every two paid candies, you may take a third free only when its cost is no greater than either paid candy. Given cost, return the minimum total payment to obtain all candies. Each candy can be used in only one such group.
