Question

2706. Buy Two Chocolates

中文文档

Description

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

Solutions

Solution 1: Sorting

We can sort the prices of the chocolates in ascending order, and then add the first two prices to get the minimum cost $cost$ of buying two chocolates. If this cost is greater than the money we have, then we return money. Otherwise, we return money - cost.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Where $n$ is the length of the array prices.

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

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

class Solution {
public:
  int buyChoco(vector<int>& prices, int money) {
    sort(prices.begin(), prices.end());
    int cost = prices[0] + prices[1];
    return money < cost ? money : money - cost;
  }
};

func buyChoco(prices []int, money int) int {
  sort.Ints(prices)
  cost := prices[0] + prices[1]
  if money < cost {
    return money
  }
  return money - cost
}

function buyChoco(prices: number[], money: number): number {
  prices.sort((a, b) => a - b);
  const cost = prices[0] + prices[1];
  return money < cost ? money : money - cost;
}

impl Solution {
  pub fn buy_choco(mut prices: Vec<i32>, money: i32) -> i32 {
    prices.sort();
    let cost = prices[0] + prices[1];
    if cost > money {
      return money;
    }
    money - cost
  }
}

Solution 2: One-pass Traversal

We can find the two smallest prices in one pass, and then calculate the cost.

The time complexity is $O(n)$, where $n$ is the length of the array prices. The space complexity is $O(1)$.

class Solution:
  def buyChoco(self, prices: List[int], money: int) -> int:
    a = b = inf
    for x in prices:
      if x < a:
        a, b = x, a
      elif x < b:
        b = x
    cost = a + b
    return money if money < cost else money - cost

class Solution {
  public int buyChoco(int[] prices, int money) {
    int a = 1000, b = 1000;
    for (int x : prices) {
      if (x < a) {
        b = a;
        a = x;
      } else if (x < b) {
        b = x;
      }
    }
    int cost = a + b;
    return money < cost ? money : money - cost;
  }
}

class Solution {
public:
  int buyChoco(vector<int>& prices, int money) {
    int a = 1000, b = 1000;
    for (int x : prices) {
      if (x < a) {
        b = a;
        a = x;
      } else if (x < b) {
        b = x;
      }
    }
    int cost = a + b;
    return money < cost ? money : money - cost;
  }
};

func buyChoco(prices []int, money int) int {
  a, b := 1001, 1001
  for _, x := range prices {
    if x < a {
      a, b = x, a
    } else if x < b {
      b = x
    }
  }
  cost := a + b
  if money < cost {
    return money
  }
  return money - cost
}

function buyChoco(prices: number[], money: number): number {
  let [a, b] = [1000, 1000];
  for (const x of prices) {
    if (x < a) {
      b = a;
      a = x;
    } else if (x < b) {
      b = x;
    }
  }
  const cost = a + b;
  return money < cost ? money : money - cost;
}

impl Solution {
  pub fn buy_choco(prices: Vec<i32>, money: i32) -> i32 {
    let mut a = 1000;
    let mut b = 1000;
    for &x in prices.iter() {
      if x < a {
        b = a;
        a = x;
      } else if x < b {
        b = x;
      }
    }
    let cost = a + b;
    if money < cost {
      money
    } else {
      money - cost
    }
  }
}