Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1774.html
1774. Closest Dessert Cost
Level
Medium
Description
You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:
- There must be exactly one ice cream base.
- You can add one or more types of topping or have no toppings at all.
- There are at most two of each type of topping.
You are given three inputs:
baseCosts, an integer array of lengthn, where eachbaseCosts[i]represents the price of thei-thice cream base flavor.toppingCosts, an integer array of lengthm, where eachtoppingCosts[i]is the price of one of thei-thtopping.target, an integer representing your target price for dessert.
You want to make a dessert with a total cost as close to target as possible.
Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.
Example 1:
Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10
Output: 10
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 7
- Take 1 of topping 0: cost 1 x 3 = 3
- Take 0 of topping 1: cost 0 x 4 = 0
Total: 7 + 3 + 0 = 10.
Example 2:
Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
Output: 17
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 3
- Take 1 of topping 0: cost 1 x 4 = 4
- Take 2 of topping 1: cost 2 x 5 = 10
- Take 0 of topping 2: cost 0 x 100 = 0
Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.
Example 3:
Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9
Output: 8
Explanation: It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.
Example 4:
Input: baseCosts = [10], toppingCosts = [1], target = 1
Output: 10
Explanation: Notice that you don’t have to have any toppings, but you must have exactly one base.
Constraints:
n == baseCosts.lengthm == toppingCosts.length1 <= n, m <= 101 <= baseCosts[i], toppingCosts[i] <= 10^41 <= target <= 10^4
Solution
Loop over all possible combinations of toppingCosts, where each topping has count 0, 1 or 2. For each combination, calculate the total cost of toppings, and loop over baseCosts to calculate all possible values of total cost. Find the closest cost among all possible values and return the closest cost.
-
class Solution { public int closestCost(int[] baseCosts, int[] toppingCosts, int target) { int closest = Integer.MAX_VALUE; for (int baseCost : baseCosts) closest = Math.min(closest, baseCost); int minDifference = Math.abs(closest - target); int toppingsCount = toppingCosts.length; int totalToppings = (int) Math.pow(3, toppingsCount); for (int i = 0; i < totalToppings; i++) { int[] combination = getCombination(toppingsCount, i); int toppingCost = getToppingCost(toppingCosts, combination); for (int baseCost : baseCosts) { int totalCost = toppingCost + baseCost; int difference = Math.abs(totalCost - target); if (difference < minDifference || difference == minDifference && totalCost < closest) { closest = totalCost; minDifference = difference; } } } return closest; } public int[] getCombination(int length, int index) { int[] combination = new int[length]; for (int i = length - 1; i >= 0 && index > 0; i--) { int remainder = index % 3; combination[i] = remainder; index /= 3; } return combination; } public int getToppingCost(int[] toppingCosts, int[] combination) { int cost = 0; int length = toppingCosts.length; for (int i = 0; i < length; i++) cost += toppingCosts[i] * combination[i]; return cost; } } ############ class Solution { private List<Integer> arr = new ArrayList<>(); private int[] ts; private int inf = 1 << 30; public int closestCost(int[] baseCosts, int[] toppingCosts, int target) { ts = toppingCosts; dfs(0, 0); Collections.sort(arr); int d = inf, ans = inf; for (int x : baseCosts) { for (int y : arr) { int i = search(target - x - y); for (int j : new int[] {i, i - 1}) { if (j >= 0 && j < arr.size()) { int t = Math.abs(x + y + arr.get(j) - target); if (d > t || (d == t && ans > x + y + arr.get(j))) { d = t; ans = x + y + arr.get(j); } } } } } return ans; } private int search(int x) { int left = 0, right = arr.size(); while (left < right) { int mid = (left + right) >> 1; if (arr.get(mid) >= x) { right = mid; } else { left = mid + 1; } } return left; } private void dfs(int i, int t) { if (i >= ts.length) { arr.add(t); return; } dfs(i + 1, t); dfs(i + 1, t + ts[i]); } } -
// OJ: https://leetcode.com/problems/closest-dessert-cost/ // Time: O(B * 3^T) // Space: O(T) class Solution { int ans, diff; void dfs(vector<int> &T, int i, int sum, int target) { int d = abs(sum - target); if (d > diff && sum > ans) return; if (d < diff || (d == diff && sum < ans)) { ans = sum; diff = d; } if (i == T.size()) return; for (int j = 0; j <= 2; ++j) dfs(T, i + 1, sum + j * T[i], target); } public: int closestCost(vector<int>& B, vector<int>& T, int target) { ans = B[0]; diff = abs(target - ans); for (int b : B) dfs(T, 0, b, target); return ans; } }; -
class Solution: def closestCost( self, baseCosts: List[int], toppingCosts: List[int], target: int ) -> int: def dfs(i, t): if i >= len(toppingCosts): arr.append(t) return dfs(i + 1, t) dfs(i + 1, t + toppingCosts[i]) arr = [] dfs(0, 0) arr.sort() d = ans = inf for x in baseCosts: for y in arr: i = bisect_left(arr, target - x - y) for j in (i, i - 1): if 0 <= j < len(arr): t = abs(x + y + arr[j] - target) if d > t or (d == t and ans > x + y + arr[j]): d = t ans = x + y + arr[j] return ans ############ # 1774. Closest Dessert Cost # https://leetcode.com/problems/closest-dessert-cost/ class Solution: res = float('inf') def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int: n = len(toppingCosts) def helper(current, index): if abs(target - current) < abs(target - self.res) or (abs(target - current) == abs(target - self.res) and current < self.res): self.res = current if index == n or current > target: return helper(current, index + 1) helper(current + toppingCosts[index], index + 1) helper(current + toppingCosts[index] * 2, index + 1) for base in baseCosts: helper(base, 0) return self.res -
func closestCost(baseCosts []int, toppingCosts []int, target int) int { arr := []int{} var dfs func(int, int) dfs = func(i, t int) { if i >= len(toppingCosts) { arr = append(arr, t) return } dfs(i+1, t) dfs(i+1, t+toppingCosts[i]) } dfs(0, 0) sort.Ints(arr) const inf = 1 << 30 ans, d := inf, inf for _, x := range baseCosts { for _, y := range arr { i := sort.Search(len(arr), func(i int) bool { return arr[i] >= target-x-y }) for j := i - 1; j < i+1; j++ { if j >= 0 && j < len(arr) { t := abs(x + y + arr[j] - target) if d > t || (d == t && ans > x+y+arr[j]) { d = t ans = x + y + arr[j] } } } } } return ans } func abs(x int) int { if x < 0 { return -x } return x }