#2735

Medium

LeetCode Problem Workspace

Collecting Chocolates

Calculate the minimum cost to collect all chocolate types using rotations and purchases in an array-based enumeration pattern.

array enumeration

Problem Statement

You are given a 0-indexed array nums where nums[i] represents the cost of collecting the ith type of chocolate. You may purchase chocolates directly at their listed cost.

In one operation costing x, you can rotate the chocolate types by moving each chocolate one position forward in the array cyclically. You can perform any number of rotations. Return the minimum total cost to collect at least one of each chocolate type.

Examples

Example 1

Input: nums = [20,1,15], x = 5

Output: 13

Initially, the chocolate types are [0,1,2]. We will buy the 1st type of chocolate at a cost of 1. Now, we will perform the operation at a cost of 5, and the types of chocolates will become [1,2,0]. We will buy the 2nd type of chocolate at a cost of 1. Now, we will again perform the operation at a cost of 5, and the chocolate types will become [2,0,1]. We will buy the 0th type of chocolate at a cost of 1. Thus, the total cost will become (1 + 5 + 1 + 5 + 1) = 13. We can prove that this is optimal.

Example 2

Input: nums = [1,2,3], x = 4

Output: 6

We will collect all three types of chocolates at their own price without performing any operations. Therefore, the total cost is 1 + 2 + 3 = 6.

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 109
1 <= x <= 109

Solution Approach

Direct Purchase vs Rotations

Compare the cost of buying each chocolate immediately against performing rotations. Use array enumeration to track the total cost for each rotation count, ensuring minimal cumulative expense.

Enumerate Rotation Scenarios

For each rotation from 0 up to n-1, compute the effective cost of each chocolate at its new position. Sum the costs including rotation costs to find the total expense for that scenario.

Select Optimal Sequence

After calculating total costs for all rotation counts, choose the scenario with the lowest combined purchase and rotation costs. This ensures the solution uses the array plus enumeration pattern efficiently without redundant operations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) because for each of n rotations, we may sum costs across n elements. Space complexity is O(n) for storing rotated cost arrays and tracking totals.

What Interviewers Usually Probe

Will you consider the rotation cost when deciding which chocolate to pick first?
How many rotations will be necessary at maximum before costs repeat?
Can you optimize the calculation of cumulative costs across rotations using enumeration?

Common Pitfalls or Variants

Common pitfalls

Forgetting to include the rotation cost x in total calculations.
Overcounting purchases when a rotation shifts already collected chocolates.
Failing to check all possible rotation counts for minimal total cost.

Follow-up variants

Minimize total cost when multiple chocolates of the same type exist with different prices.
Compute minimum cost if rotations are restricted to k times only.
Find total cost if some chocolates cannot be rotated due to constraints.

FAQ

What is the best approach to solve Collecting Chocolates?

Use array enumeration to evaluate all possible rotations and combine rotation and purchase costs to find the minimal total.

How do rotations affect the total cost in Collecting Chocolates?

Each rotation costs x, shifting chocolate types; optimal sequences minimize overall cost by balancing rotation versus direct purchase.

Can this problem be solved without considering every rotation?

No, you must enumerate each rotation scenario because the minimal cost depends on how rotations redistribute chocolate positions.

What is the main pattern used in this problem?

The problem relies on the Array plus Enumeration pattern, iterating over all rotation sequences to calculate minimal collection cost.

What common mistakes should I avoid?

Do not forget to include rotation costs, overcount chocolates already collected, or skip evaluating some rotation sequences.

terminal

Solution

Solution 1: Enumeration

We consider enumerating the number of operations, and define $f[i][j]$ as the minimum cost after the $i$-th chocolate has undergone $j$ operations.

1

2

3

4

5

6

7

8

9

class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        f = [[0] * n for _ in range(n)]
        for i, v in enumerate(nums):
            f[i][0] = v
            for j in range(1, n):
                f[i][j] = min(f[i][j - 1], nums[(i - j) % n])
        return min(sum(f[i][j] for i in range(n)) + x * j for j in range(n))

Continue Practicing

#2761 prime pairs with target sum #2708 maximum strength of a group #2765 longest alternating subarray