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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int *)a - *(int *)b);
6}
7
8int buyTwoChocolates(int* prices, int pricesSize, int money) {
9 qsort(prices, pricesSize, sizeof(int), compare);
10 int left = 0, right = pricesSize - 1;
11 int minSpent = INT_MAX;
12
13 while (left < right) {
14 int sum = prices[left] + prices[right];
15 if (sum <= money) {
16 minSpent = sum;
17 left++;
18 } else {
19 right--;
20 }
21 }
22 return (minSpent == INT_MAX) ? money : money - minSpent;
23}
24
25int main() {
26 int prices[] = {1, 2, 2};
27 int money = 3;
28 printf("%d\n", buyTwoChocolates(prices, 3, money));
29 return 0;
30}The array is sorted, and two pointers are used to traverse the array. The goal is to find two minimal-priced chocolates within the budget. Adjusting pointers appropriately allows us to find the correct pair, and calculation of remaining money is straightforward. If no valid pair is found, the function returns the original amount of 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.
1using System;
2
3class Program {
4 public static int BuyTwoChocolates(int[] prices, int money) {
5 int minSpent = money + 1;
6 for (int i = 0; i < prices.Length; i++) {
7 for (int j = i + 1; j < prices.Length; j++) {
8 int sum = prices[i] + prices[j];
9 if (sum <= money && sum < minSpent) {
10 minSpent = sum;
11 }
12 }
13 }
14 return (minSpent > money) ? money : money - minSpent;
15 }
16
17 static void Main() {
18 int[] prices = { 3, 2, 3 };
19 int money = 3;
20 Console.WriteLine(BuyTwoChocolates(prices, money));
21 }
22}This C# brute force method iterates through each pair of prices to find the lowest viable cost of buying two chocolates, ensuring funds are enough.