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

Closest Dessert Cost

Number: 1900

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a list of ice cream base costs and topping costs, where you must choose exactly one base and may add 0 or more toppings (with up to two of each topping allowed), determine the total dessert cost that is closest to a target value. If there are ties, choose the lower cost.

Key Insights

  • The base cost must be chosen exactly once; toppings are optional and each topping can be used 0, 1, or 2 times.
  • There are at most 3^m topping combinations (m ≤ 10), which is feasible with a backtracking/DFS approach.
  • Use DFS (or recursion) to generate all valid topping additions for each base and update an answer based on how close it is to the target.
  • If the current cost exceeds the target in a DFS branch, further additions will only increase the difference, so that branch can be pruned.

Space and Time Complexity

Time Complexity: O(n * 3^m), where n is the number of bases and m is the number of toppings. Space Complexity: O(m), which is the recursion depth in the DFS.

Solution

We iterate over each base cost and use a recursive DFS to explore the three possibilities (0, 1, or 2 of each topping) for every topping in toppingCosts. A global (or an outer scoped) variable tracks the best dessert cost found so far. In the DFS, we update this best cost by comparing the absolute differences between the current cost and the target. To optimize, if the current cost exceeds the target, further topping additions will only worsen the difference, so the recursion can stop early. This approach covers all valid combinations and ensures we choose the closest cost (or the lower one in the event of a tie).

Code Solutions

# Python solution for Closest Dessert Cost
def closestCost(baseCosts, toppingCosts, target):
    best = None

    # Update the best cost found so far 
    def update(cost):
        nonlocal best
        # If best is None, or found a closer cost, or same difference with lower cost
        if best is None or abs(cost - target) < abs(best - target) or (abs(cost - target) == abs(best - target) and cost < best):
            best = cost

    # DFS helper function to explore topping possibilities starting from index i
    def dfs(i, currentCost):
        update(currentCost)
        # Prune if currentCost already exceeds target, further addition only gets worse.
        if i == len(toppingCosts) or currentCost >= target:
            return
        # For each topping, try using it 0, 1, or 2 times.
        dfs(i + 1, currentCost)                                # 0 of this topping
        dfs(i + 1, currentCost + toppingCosts[i])              # 1 of this topping
        dfs(i + 1, currentCost + 2 * toppingCosts[i])          # 2 of this topping

    # Iterate through each base cost and perform DFS on toppings.
    for base in baseCosts:
        dfs(0, base)
    
    return best

# Example usage:
if __name__ == '__main__':
    print(closestCost([1,7], [3,4], 10))   # Expected output: 10
    print(closestCost([2,3], [4,5,100], 18)) # Expected output: 17
    print(closestCost([3,10], [2,5], 9))     # Expected output: 8
← Back to All Questions