D
DevExCode

LeetCode 1774: Closest Dessert Cost Solution

Master LeetCode problem 1774 (Closest Dessert Cost), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1774. Closest Dessert Cost

Medium
ArrayDynamic ProgrammingBacktracking

Problem Explanation

Explanation:

To solve this problem, we can use a recursive approach to try all possible combinations of ice cream base flavors and toppings. We will iterate through each ice cream base flavor and for each flavor, we will try all possible combinations of toppings (including not selecting any topping). We will keep track of the closest cost to the target and return the closest cost found.

Detailed Steps:

  1. Define a recursive function that takes the current cost, index of the current base flavor, and index of the current topping as parameters.
  2. In the recursive function, iterate through all possible combinations of toppings (including not selecting any topping) and calculate the total cost.
  3. Update the closest cost found so far.
  4. Base cases:
    • If the total cost equals the target, return the target as the closest cost.
    • If the total cost is greater than the target or we have considered all toppings, return the current cost as the closest cost.
  5. Recur by trying the next topping with the same base flavor and also by moving to the next base flavor.
  6. Return the closest cost found.

Time Complexity:

The time complexity of this approach is O(2^m * n) where n is the number of ice cream base flavors and m is the number of types of toppings.

Space Complexity:

The space complexity of this approach is O(m) for the recursive stack.

:

Solution Code

class Solution {
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        int closestCost = Integer.MAX_VALUE;
        for (int baseCost : baseCosts) {
            closestCost = Math.min(closestCost, calculateCost(baseCost, 0, toppingCosts, target));
        }
        return closestCost;
    }
    
    private int calculateCost(int currentCost, int toppingIndex, int[] toppingCosts, int target) {
        if (toppingIndex == toppingCosts.length) {
            return currentCost;
        }
        
        int cost1 = calculateCost(currentCost, toppingIndex + 1, toppingCosts, target);
        int cost2 = calculateCost(currentCost + toppingCosts[toppingIndex], toppingIndex + 1, toppingCosts, target);
        int cost3 = calculateCost(currentCost + 2 * toppingCosts[toppingIndex], toppingIndex + 1, toppingCosts, target);
        
        int closestCost = Math.abs(cost1 - target) < Math.abs(cost2 - target) ? cost1 : cost2;
        closestCost = Math.abs(closestCost - target) < Math.abs(cost3 - target) ? closestCost : cost3;
        
        return closestCost;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1774 (Closest Dessert Cost)?

This page provides optimized solutions for LeetCode problem 1774 (Closest Dessert Cost) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1774 (Closest Dessert Cost)?

The time complexity for LeetCode 1774 (Closest Dessert Cost) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1774 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1774 in Java, C++, or Python.

Back to LeetCode Solutions