Buy Two Chocolates

Problem Statement

In this problem, you are provided with an array of integers called prices, representing the cost of different chocolates in a store. Alongside, you are given a single integer money representing the total amount of money you have. The objective is to purchase exactly two chocolates from this list. However, the sum of the prices of these two chocolates should allow you to have some money left, specifically a non-negative amount. Your goal is to spend as much of your money as possible on these two chocolates without going into debt, thereby minimizing the leftover money after the purchase. If it's not possible to buy two chocolates without exceeding your budget, simply return the initial amount of money you have. The solution should effectively determine the optimal pair of chocolates to purchase, so that the leftover money is minimized.

Examples

Example 1

Input:

prices = [1,2,2], money = 3

Output:

0

Explanation:

Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 - 3 = 0 units of money afterwards. Thus, we return 0.

Example 2

Input:

prices = [3,2,3], money = 3

Output:

3

Explanation:

You cannot buy 2 chocolates without going in debt, so we return 3.

Constraints

• 2 <= prices.length <= 50
• 1 <= prices[i] <= 100
• 1 <= money <= 100

Approach and Intuition

To solve this problem optimally, consider the following approach based on the given constraints:

1. If there are only two chocolates in the list (prices.length == 2), simply sum their costs. If the sum is less than or equal to money, return the remaining amount after the purchase. If greater, return the initial amount of money as no purchase is possible without debt.
2. For more chocolates, iterate through each possible combination of two distinct chocolates:
   • For each combination (let’s say chocolates at i and j with i < j), calculate the combined cost.
   • If this combined cost is less than or equal to your money:
     • Check how much money will be leftover after this purchase.
     • Keep track of the maximum amount spent in order to minimize the leftover money.
   • If no valid pairs are found (all combinations exceed the budget), the returned result should be the original amount of money, indicating that no purchase is feasible.

This method ensures that you check all possible pairs and find the one that maximizes your expenditure without going into debt. In computational terms, this algorithm runs in O(n^2) time complexity because every pair of chocolates is considered exactly once, where n refers to the total number of chocolates, which is feasible given the constraint (maximum of 50 chocolates). This brute-force approach ensures that you find the solution by explicitly checking each viable pair.

Solutions

class Solution {
public:
    int purchaseChocolates(vector<int>& costList, int budget) {
        int cheapest = min(costList[0], costList[1]);
        int secondCheapest = max(costList[0], costList[1]);
    
        for (int idx = 2; idx < costList.size(); idx++) {
            if (costList[idx] < cheapest) {
                secondCheapest = cheapest;
                cheapest = costList[idx];
            } else if (costList[idx] < secondCheapest) {
                secondCheapest = costList[idx];
            }
        }
    
        int totalMinimumCost = cheapest + secondCheapest;
    
        if (totalMinimumCost <= budget) {
            return budget - totalMinimumCost;
        }
    
        return budget;
    }
};