Problem Statement
There are some items you want to purchase from a store.
The prices of these items are given in the
You can purchase any item by paying its price.
However, the store also has a special sale today: "buy one, get one free". This means that whenever you bring a pair of items to the cash register, you only have to pay for the more expensive one and you'll get the other one for free as a bonus.
Given the prices, find the optimal shopping strategy and calculate the minimum you have to pay to purchase all the items you want.
Definition
- Class:
- BuyOneGetOneFree
- Method:
- buy
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int buy(int[] prices)
- (be sure your method is public)
Constraints
- prices will contain between 1 and 10 elements, inclusive.
- Each element of prices will be between 1 and 1000, inclusive.
Examples
{47}
Returns: 47
There is a single item you want. There is no way to use the sale, you just have to pay for it.
{10, 20}
Returns: 20
You want two items. One costs 10, the other 20. You can use the sale to pay just 20 and get both of them.
{10, 20, 30, 20}
Returns: 50
You can use the sale as many times as you want (of course, always buying two new items).
{5, 7, 13, 2, 9}
Returns: 22
If you are clever, you will only pay 13 + 7 + 2 for these five items.
{441, 567, 465, 585, 352, 264, 525}
Returns: 1815
{6, 24, 81, 1, 348, 133, 51, 12}
Returns: 459
{564, 594, 781, 280, 634}
Returns: 1655
{233, 6, 19}
Returns: 239
{103, 13, 1, 102, 171, 1, 58, 1, 41, 40}
Returns: 328
{234, 5, 14, 106, 12, 4, 8, 21}
Returns: 272
{952, 433, 484, 813, 203}
Returns: 1639
{117, 620, 578, 835, 13, 258}
Returns: 1530
{546, 382, 483, 939, 987, 220, 341, 411, 934, 40}
Returns: 3006
{3, 4, 15, 112, 2, 370, 32, 896}
Returns: 1026
{17, 160, 6, 990, 1, 784, 165, 6, 81, 6}
Returns: 1248
{700, 505, 508, 80, 391}
Returns: 1285
{109, 909}
Returns: 909
{52, 24, 3, 17, 24, 5, 3, 1}
Returns: 84
{5, 60, 1, 899, 59, 1}
Returns: 959
{821, 346, 407, 881, 545, 311, 731, 203, 260, 70}
Returns: 2533
{179, 626}
Returns: 626
{63, 100, 50, 92, 53, 1, 566}
Returns: 712
{577, 269, 705, 265, 181}
Returns: 1155
{108, 362, 2, 14, 10, 78, 1}
Returns: 451
{776, 799, 308, 2, 31, 172, 14, 23, 6}
Returns: 1154
{931, 61}
Returns: 931
{26, 19, 186, 1, 36, 22, 3, 1, 95, 5}
Returns: 250
{364, 964, 937, 611}
Returns: 1575
{8, 3, 348, 2, 2, 96, 3, 3, 24, 7}
Returns: 384
{102, 392, 91, 31, 11, 7, 18}
Returns: 508
{164, 67, 176, 69, 873, 196, 217, 189, 590}
Returns: 1510
{5, 2, 4, 3, 158}
Returns: 164
{25, 205, 399, 175, 692, 721, 692, 692}
Returns: 1987
{40, 243, 678, 21, 215, 80, 864, 437, 422}
Returns: 1645
{594, 843, 141, 485, 575}
Returns: 1559
{164, 913, 808, 318, 81, 680, 901, 443, 697}
Returns: 2800
{735, 297, 999, 579, 78, 1, 1, 3}
Returns: 1657
{44, 512, 471, 212, 768, 788, 121, 594, 411}
Returns: 2109
{764, 221, 6, 3, 6, 203, 157}
Returns: 976
{13, 49, 8, 805, 1, 643, 200, 2}
Returns: 1020
{2, 8}
Returns: 8
{780, 141, 618, 38, 585, 476, 985, 252, 327, 479}
Returns: 2550
{211, 1, 8, 282, 23, 379, 221}
Returns: 624
{89, 103, 1, 1, 433, 79, 23}
Returns: 546
{496, 388, 800, 569, 646, 135, 624, 354, 724, 313}
Returns: 2716
{537, 14}
Returns: 537
{55, 603, 915}
Returns: 970
{984, 318, 117, 998, 457, 813, 491, 604, 641, 329}
Returns: 3190
{9, 48, 13, 2, 1}
Returns: 58
{684, 761, 699, 212, 239, 117}
Returns: 1657
{57, 73, 2}
Returns: 75
{887, 521, 501, 368, 576, 362, 997, 332, 444, 2}
Returns: 2774
{944, 348, 623, 908, 34, 926}
Returns: 2200
{422, 311}
Returns: 422
{100, 100, 100, 100, 100, 100}
Returns: 300
If you take two items that cost the same, you can still pay for one of them and get the other one for free. These six items are best bought as three separate pairs.
{45, 46, 47, 48, 49 }
Returns: 141
{10, 20, 30, 20 }
Returns: 50
{5, 7, 13, 2, 9 }
Returns: 22
{10, 20, 30, 40 }
Returns: 60
{10, 20, 30, 40, 50 }
Returns: 90