Third One Free
A shop has an offer: bring three items to the till together and the cheapest of the three is free. You want to buy every item in prices. You may split your shopping into groups of up to three items in any way you like. A group of exactly three gets its cheapest item free, and a smaller group pays for everything.
Return the smallest total you can pay.
Example 1
prices [6,4,9]
returns 15
All three go together. The cheapest one, 4, is free, so you pay 9 + 6 = 15.
Example 2
prices [5,5]
returns 10
Two items do not make a group of three, so you pay 5 + 5 = 10.
Example 3
prices [8,2,7,3,9,1]
returns 22
Group 9, 8 and 7 so that the 7 is free, then 3, 2 and 1 so that the 1 is free. You pay 9 + 8 + 3 + 2 = 22.
Constraints
0 <= len(prices) <= 301 <= prices[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.