A bazaar vendor is running a promotion for shoppers buying several items in one visit: any three items selected together as a bundle let the shopper take the cheapest of the three home for free (the other two in that bundle are paid at full price). Items that cannot be grouped into a complete bundle of three must be paid for individually at full price. Given the price of every item you plan to buy, decide how to group your items into bundles of three, with any leftover one or two items paid individually, so as to minimize the total amount you pay.
n, the number of items.n space-separated integers, the price of each item.A single integer: the minimum total amount that must be paid to acquire every item.
Example 1
Input
3 1 2 3
Expected
5
Explanation
All three items form one bundle. Sorted descending: 3, 2, 1. The two priciest items (3 and 2) are paid for, and the cheapest (1) is free. Total = 3 + 2 = 5.
Example 2
Input
6 6 5 7 9 2 2
Expected
23
Explanation
Sorted descending: 9, 7, 6, 5, 2, 2. Grouping the first three (9, 7, 6) as one bundle frees the 6, and the next three (5, 2, 2) as another bundle frees one of the 2's. Paid items: 9 + 7 + 5 + 2 = 23.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →