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.
1import java.util.Arrays;
2
3public class BuyChocolates {
4 public static int buyTwoChocolates(int[] prices, int money) {
5 Arrays.sort(prices);
6 int left = 0, right = prices.length - 1;
7 int minSpent = Integer.MAX_VALUE;
8
9 while (left < right) {
10 int sum = prices[left] + prices[right];
11 if (sum <= money) {
12 minSpent = sum;
13 left++;
14 } else {
15 right--;
16 }
17 }
18 return (minSpent == Integer.MAX_VALUE) ? money : money - minSpent;
19 }
20
21 public static void main(String[] args) {
22 int[] prices = {1, 2, 2};
23 int money = 3;
24 System.out.println(buyTwoChocolates(prices, money));
25 }
26}Java's Arrays.sort() is used for initial sorting. Two pointers iterate to minimize the sum of the chosen chocolates. Depending on the sum comparison with money, pointers are adjusted for an optimal solution.
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 <stdio.h>
2
3int buyTwoChocolates(int* prices, int pricesSize, int money) {
4 int minSpent = money + 1;
5 for (int i = 0; i < pricesSize; i++) {
6 for (int j = i + 1; j < pricesSize; j++) {
7 int sum = prices[i] + prices[j];
8 if (sum <= money && sum < minSpent) {
9 minSpent = sum;
10 }
11 }
12 }
13 return (minSpent > money) ? money : money - minSpent;
14}
15
16int main() {
17 int prices[] = {3, 2, 3};
18 int money = 3;
19 printf("%d\n", buyTwoChocolates(prices, 3, money));
20 return 0;
21}Iterate through each possible pair in the prices array using two for loops. If a pair is more affordable than previously found and within budget, update the tracking minimum.