#2735
Collecting Chocolates
expert · 1130 · lc medium +32 · verified · 34.7% accepted · 312 likes · top 12%
Description
You have n chocolates where nums[i] is the collection cost of position i, initially holding type i. One operation (cost x) cyclically shifts all types by one: type at position i becomes (i + 1) mod n. Perform any number of operations and collect each type at minimum cost. Return the minimum total cost.
Example 1:
Input: nums = [20,1,15], x = 5
Output: 13
Explanation: 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
Explanation: 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.
Code
1
2
3