Third one free cart
EasyOnline Assessment
Work out the total at checkout for a "buy 2, get the 3rd free" promotion on one family of products.
The shop prices everything in whole cents. Every item in the cart is part of the promotion, with two conditions:
- An item priced below
floorcents is too cheap to take part: it is never counted towards a group of three and can never be free. It is simply paid for in full. - Among the remaining items, the cashier forms groups of three starting from the most expensive items: the three priciest form the first group, the next three priciest form the second group, and so on. In every complete group the cheapest item is free. Items left over that do not fill a group of three are paid for in full.
The promotion can give away at most cap free items per order. If more groups qualify, only the first cap groups (the most expensive ones) get their free item.
Input:
prices: the price in cents of each item in the cart, in scan order.floor: the minimum price in cents for an item to take part.cap: the maximum number of free items.
Output: a list [to_pay, saved]: the total in cents the customer pays, and the total in cents saved by free items. An empty cart returns [0, 0].
Example 1
- Input:
- [[200,900,400,800,300,700],100,5]
- Output:
- [2400,900]
- Explanation
- All six prices clear the floor of 100. Sorted from the top: 900, 800, 700 | 400, 300, 200. The cheapest item of each group (700 and 200) is free, and the cap of 5 allows both. The cart totals 3300, so the customer saves 900 and pays 2400.
Example 2
- Input:
- [[300,50,500,100,300,400],100,5]
- Output:
- [1350,300]
- Explanation
- The 50 is below the floor of 100, so it never takes part and is paid in full. The eligible prices sorted are 500, 400, 300, 300, 100. Only 500, 400, 300 form a complete group, and its cheapest item (300) is free. The leftover 300 and 100 are paid in full. The cart totals 1650, so the answer is
[1350, 300].
Example 3
- Input:
- [[700,100,400,900,800,400,600,1000,300],100,2]
- Output:
- [4000,1200]
- Explanation
- All prices clear the floor. Sorted: 1000, 900, 800 | 700, 600, 400 | 400, 300, 100. Three groups qualify, with free items 800, 400 and 100, but the cap is 2, so only the two most expensive groups give theirs: saved 800 + 400 = 1200. The cart totals 5200, so the answer is
[4000, 1200].
Constraints
0 <= len(prices) <= 601 <= prices[i] <= 1000001 <= floor <= 1000000 <= cap <= 30