Pay for Two, Take a Third

Easy

A bookshop runs a promotion: buy two books and take a third one for free. The free book must cost no more than the **cheaper** of the two books bought. You are given an array prices with the prices of all the books a customer wants to take home. Each book is either paid for or taken under the promotion, and every pair bought earns at most one free book. Return the minimum total the customer has to pay for all of them.

Example 1

prices=[4, 8, 3, 7, 2] → 20

Buy 8 and 7 and take 4 for free. Then buy 3 and 2; there is no third item left to get for free. The total is 8 + 7 + 3 + 2 = 20.

Example 2

prices=[5, 5, 5, 5, 5, 5] → 20

Two groups of three: in each one we pay for two items, so the total is 4 × 5 = 20.

Example 3

prices=[9] → 9

Constraints

1 ≤ len(prices) ≤ 100
1 ≤ prices[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Cake Slices for Guests Easy Strength of the Weaker Partner Easy Triangle From Sticks Easy Sign Flips for the Largest Sum Easy Pack the Backpack Easy

Input

prices=[4, 8, 3, 7, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.