140. Minimum and Maximum Amount to Buy All N Candies

A shop sells n candies with given costs. There's an offer: for every candy you pay for, you may take k other candies for free. Find the minimum amount needed to buy all the candies, and separately the maximum amount you could end up paying if you always chose the worst valid strategy. Print 'min max'.

Input: The first line contains an integer n, the number of candies. The second line contains n space-separated integers, the candy costs. The final line contains k, the number of free candies given per paid candy. Output: Print two space-separated integers - the minimum amount and the maximum amount needed to buy all candies.

1 <= n <= 10^5, 0 <= k < n

Both the minimize and maximize objectives use the exact SAME sorted array and a similar two-pointer sweep - only the direction of which end you 'pay for' versus 'take free' flips between the two.

Find both the cheapest and priciest way to buy all candies under a 'buy one get k free' offer. Brute force: Try every possible order of purchases and every possible choice of which candies to take free at each step - this is combinatorially expensive, when a simple sorted two-pointer approach directly gives both optimal answers. Optimised: Sorting once and then using two pointers (one from each end, moving toward the middle) directly simulates the greedy strategy for BOTH minimize and maximize cases - always pairing the 'paid' choice from one end with the 'free' choices from the other end in the appropriate direction for each objective.

Sort the array ascending in O(n log n). For the minimum amount, use two pointers i = 0 and j = n-1: pay for arr[i], then jump j backward by k (those become free), and advance i forward by one, repeating until the pointers cross, summing the paid values. For the maximum amount, pay for arr[j] (the costliest remaining) and jump i forward by k (those become free), advancing j backward by one, repeating until the pointers cross. Each pointer only ever moves forward or backward, so both simulations complete in a single linear pass with only index arithmetic and no explicit deletions. Time: O(n log n) (dominated by the sort) Space: O(1) extra

Recursively try every possible order and choice of which remaining candy to 'pay' for at each step, and for each choice, try every valid choice of which k other remaining candies to take for free, exploring the full space of buying strategies. Track the minimum total paid across all explored strategies (for the minimum amount) and the maximum total paid across all strategies (for the maximum amount, i.e. the worst valid way to satisfy the offer). This exhaustively respects the offer's rules but branches combinatorially. Time: Exponential, roughly O(2^n) or worse Space: O(n) recursion depth

Sort the array once in O(n log n). For the minimum, repeatedly take the current cheapest remaining candy as the one paid for and remove it along with the k current most expensive remaining candies from an explicit working list, repeating until the list is empty and summing the paid amounts; do the symmetric process (pay for the costliest, remove the k cheapest) for the maximum. Because each round performs an explicit removal from a list-like structure and re-derives the current boundaries, this still costs proportional work per round even though the array is pre-sorted. Time: O(n log n + n^2/(k+1)) Space: O(n)

1. To MINIMIZE: sort ascending. Always pay for the CHEAPEST remaining candy, and take the k MOST EXPENSIVE remaining candies free - this way, the priciest items always ride free. 2. To MAXIMIZE: sort ascending. Always pay for the MOST EXPENSIVE remaining candy, and take the k CHEAPEST remaining candies free - this way, the priciest items always get paid for. 3. Repeat each strategy until all candies are accounted for, summing what was actually paid.

Time: O(n log n), dominated by the sort - both the minimize and maximize simulations afterward are O(n). Space: O(1) extra space beyond the sorted array (using two pointers).

k = 0 (no free candies, min equals max), n small enough that k+1 covers all candies in one purchase, and n at its maximum of 10^5 to confirm the sort-based approach runs efficiently.

Be ready to explain both strategies clearly and why they're mirror images of each other (in the min case, the priciest items ride free; in the max case, the priciest items are what you pay for) - understanding WHY reveals the full picture of this problem.