We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Buy Two Chocolates

Number: 2756

Difficulty: Easy

Paid? No

Companies: Amazon, Microsoft

Problem Description

Given an array of chocolate prices and an initial amount of money, you must buy exactly two chocolates. The goal is to minimize the sum of the prices of the two chocolates while leaving a non-negative leftover amount of money. Return the leftover money after making the purchase, or return the original amount if no valid purchase exists.

Key Insights

  • With a small array (length at most 50), evaluating all pairs is feasible.
  • Sorting the array allows for direct access to the two smallest prices.
  • If the sum of the two smallest prices exceeds the available money, no valid purchase can be made.

Space and Time Complexity

Time Complexity: O(n log n) if sorting is used, or O(n^2) if all pairs are checked. Space Complexity: O(1) additional space (ignoring input storage).

Solution

The solution involves identifying the pair of chocolate prices that results in the minimum possible sum while ensuring that sum is less than or equal to the available money. We can achieve this by sorting the prices array and considering the two smallest values. If their sum is within the budget, the leftover is computed as money minus that sum. Otherwise, if even the cheapest pair is too expensive, return the original money amount.

For clarity:

  1. Sort the prices array.
  2. Compute the sum of the two lowest prices.
  3. If this sum is less than or equal to the available money, subtract it from money and return the result.
  4. If not, return the initial money.

This approach uses sorting as its primary data structure and leverages a simple comparison to determine affordability.

Code Solutions

# Define the function to calculate the leftover money after buying two chocolates
def buy_chocolates(prices, money):
    # Sort the prices array to get the smallest prices at the beginning
    prices.sort()  # O(n log n) time
    # Check if there are at least two chocolates
    if len(prices) < 2:
        return money  # Not enough chocolates to buy exactly two, though constraints guarantee at least 2
    # Sum the two smallest chocolate prices
    min_cost = prices[0] + prices[1]
    # If the total cost is within the budget, return the leftover money; otherwise, return the original money
    if min_cost <= money:
        return money - min_cost
    else:
        return money

# Example usage:
print(buy_chocolates([1,2,2], 3))  # Expected output: 0
print(buy_chocolates([3,2,3], 3))  # Expected output: 3
← Back to All Questions