Problem

You are given an integer array prices representing the prices of various chocolates in a store. You are also given a single integer money, which represents your initial amount of money.

You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.

Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return money. Note that the leftover must be non-negative.

Examples

Example 1

1
2
3

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

1
2
3

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

Solution

Method 1 – Sorting and Greedy

Intuition

To buy two chocolates and minimize the sum, pick the two cheapest prices. If their sum is less than or equal to money, return the leftover; otherwise, return money.

Approach

  1. Sort the prices.
  2. If the sum of the two smallest prices is less than or equal to money, return money minus that sum.
  3. Otherwise, return money.

Code

1
2
3
4
5
6
7

class Solution {
    public int buyChoco(int[] prices, int money) {
        Arrays.sort(prices);
        int total = prices[0] + prices[1];
        return total <= money ? money - total : money;
    }
}
1
2
3
4
5

class Solution:
    def buyChoco(self, prices: list[int], money: int) -> int:
        prices.sort()
        total = prices[0] + prices[1]
        return money - total if total <= money else money

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)