Sort the array of prices and use a two-pointer technique to find the two cheapest chocolates that can be bought such that their sum is less than or equal to the given amount of money. This approach helps efficiently find a solution by reducing the problem space through sorting.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the sorting is in-place.
1def buy_two_chocolates(prices, money):
2 prices.sort()
3 left, right = 0, len(prices) - 1
4 min_spent = float('inf')
5
6 while left < right:
7 sum_ = prices[left] + prices[right]
8 if sum_ <= money:
9 min_spent = sum_
10 left += 1
11 else:
12 right -= 1
13
14 return money if min_spent == float('inf') else money - min_spent
15
16prices = [1, 2, 2]
17money = 3
18print(buy_two_chocolates(prices, money))
The Python implementation sorts the list and uses two pointers to identify the minimal viable pair of chocolates. Depending on sums, the function calculates leftover money.
In this approach, check all possible pairs of chocolate prices. If a pair's sum is within the available money and minimal, update the result. Although this approach is less efficient, it is a simple and direct way to solve the problem given the constraints.
Time Complexity: O(n^2) due to the nested loop.
Space Complexity: O(1) with a few extra variables.
1#include <iostream>
2#include <vector>
3#include <climits>
4
5int buyTwoChocolates(std::vector<int>& prices, int money) {
6 int minSpent = money + 1;
7 for (size_t i = 0; i < prices.size(); ++i) {
8 for (size_t j = i + 1; j < prices.size(); ++j) {
9 int sum = prices[i] + prices[j];
10 if (sum <= money && sum < minSpent) {
11 minSpent = sum;
12 }
13 }
14 }
15 return (minSpent > money) ? money : money - minSpent;
16}
17
18int main() {
19 std::vector<int> prices = {3, 2, 3};
20 int money = 3;
21 std::cout << buyTwoChocolates(prices, money) << std::endl;
22 return 0;
23}
The brute force method involves exploring each pair via nested loops, updating the minimal sum and ensuring the selected pair does not overspend the allocated money.