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

Collecting Chocolates

Number: 2810

Difficulty: Medium

Paid? No

Companies: Deutsche Bank, Amazon

Problem Description

You are given an 0-indexed array nums where nums[i] is the cost of collecting the chocolate that initially is of type i. In one operation—with a cost x—you can simultaneously change every chocolate’s type: a chocolate of iᵗʰ type becomes of ((i + 1) mod n)ᵗʰ type. Your task is to eventually collect one chocolate of every type while incurring the minimum possible total cost. You may perform as many operations as you wish and you may choose to buy a chocolate before or after any number of operations.

Key Insights

  • A rotation (operation) shifts the “identity” (or type) of every chocolate by one (cyclically).
  • Although each chocolate has its original cost, by applying rotations you can “reuse” a relatively cheap chocolate to cover types whose original cost is high.
  • One extreme strategy is to buy each chocolate at its original price (total = sum(nums)); another is to “replace” expensive chocolates by virtually using the minimum–cost chocolate (say m) in later rounds. In doing so, every replacement “saves” some cost but requires an extra rotation cost.
  • By sorting the costs, we can try to “replace” the more expensive chocolates one by one with the cheapest chocolate’s cost m (while paying an extra x each time we do a replacement) and update the candidate answer.
  • The final answer is the minimum over the scenario where 0, 1, …, (n–1) chocolates are “replaced” (swapped out) in favor of using the minimum chocolate plus rotation costs.

Space and Time Complexity

Time Complexity: O(n log n) due to the sort
Space Complexity: O(n) if the sorted copy is taken (or O(1) additional space if sorting is done in–place)

Solution

The idea is to first compute the baseline cost by summing up all original costs (i.e. buying every chocolate in its initial state). Then, sort the array (which does not change the answer because the chocolates are “interchangeable” after rotations) so that the minimum can be identified as m = sortedNums[0]. Next, consider “replacing” some of the more expensive chocolates with the cheapest one. Every time you decide not to pay the original cost of a particular chocolate and instead virtually “replace” it with m, you save (original_cost – m). However, because the replacement requires an extra operation, you must also pay an extra cost of x.
Thus, iteratively for i = 1 to n – 1, update the “current” total cost by subtracting the extra cost paid (i.e. replacing sortedNums[i] by m) and then add the cost for the i rotations that you effectively “added” (each costing x). The answer is the minimum value found over all these possibilities.

Code Solutions

Below are implementations in Python, JavaScript, C++ and Java with detailed inline comments.

# Python solution for Collecting Chocolates
def collectingChocolates(nums, x):
    # sort the costs to easily access the minimum cost chocolate
    sorted_nums = sorted(nums)
    n = len(nums)
    # total cost if buying all chocolates at their original price
    total_cost = sum(sorted_nums)
    # answer starts as the baseline: no rotations, buying each chocolate as is
    ans = total_cost
    
    # current_cost represents making replacements in the sum using the minimum chocolate
    current_cost = total_cost
    # m is the cheapest chocolate cost
    m = sorted_nums[0]
    
    # try replacing the more expensive chocolates one by one
    for i in range(1, n):
        # replace chocolate at position i by the minimum chocolate.
        # This reduces the current sum by (sorted_nums[i] - m)
        current_cost -= (sorted_nums[i] - m)
        # Each replacement requires an extra rotation; i operations have been applied so far.
        candidate = current_cost + i * x
        # update answer with the smallest candidate cost
        ans = min(ans, candidate)
    return ans

# Example usage:
print(collectingChocolates([20, 1, 15], 5))  # Expected output: 13
print(collectingChocolates([1, 2, 3], 4))      # Expected output: 6
← Back to All Questions