2706 Buy Two Chocolates - Easy

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.

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

Problem Analysis:

• Sorting the prices takes O(n log n) time, where n is the number of chocolates.

• Accessing the first and second elements in the sorted list takes constant time.

• The overall time complexity is dominated by the sorting step: O(n log n).

• The space complexity is O(1) as the algorithm uses a constant amount of extra space.

• possible to do O(n) time complexity by doing a one-pass and keep track of the 2 minimum prices

Solutions:

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

Similar Questions