Collecting Chocolates
MedPrompt
You are given a 0-indexed integer array nums of size n representing the cost of collecting different chocolates. The cost of collecting the chocolate at the index i is nums[i]. Each chocolate is of a different type, and initially, the chocolate at the index i is of ith type.
In one operation, you can do the following with an incurred cost of x:
- Simultaneously change the chocolate of
ithtype to((i + 1) mod n)thtype for all chocolates.
Return the minimum cost to collect chocolates of all types, given that you can perform as many operations as you would like.
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.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1091 <= x <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process by checking every possible number of rotations. For each number of rotations k (from 0 to n-1), we calculate the total cost. This cost is the sum of two components: the fixed cost for performing k rotations (k * x) and the minimum cost to acquire each of the n types of chocolate, given that we can perform up to k rotations.
Algorithm
- Initialize a variable
minTotalCostto a very large value to store the minimum cost found. - Iterate through all possible numbers of rotations,
k, from0ton-1. - For each
k, calculate the cost associated with this choice: a. Start with the rotation cost, which is(long)k * x. b. For each chocolate typeifrom0ton-1, find its minimum possible acquisition cost. This involves checking its cost at0, 1, ..., krotations. c. The cost of typeiafterjrotations isnums[(i - j + n) % n]. Find the minimum of these values forjin[0, k]. d. Add this minimum cost for typeito a running sum for the currentk. - After summing the minimum costs for all types, add the rotation cost
k * xto get the total cost forkrotations. - Update
minTotalCost = min(minTotalCost, currentTotalCost). - After checking all
kfrom0ton-1,minTotalCostwill hold the answer.
Walkthrough
The fundamental idea is to exhaustively check all scenarios. A scenario is defined by the total number of rotation operations we decide to perform. Let's say we decide to perform k rotations. The cost for these operations is k * x. Once we've paid this price, we can collect each chocolate type i. For each type i, we have the choice to collect it after 0 rotations (cost nums[i]), 1 rotation (cost nums[(i-1+n)%n]), ..., or k rotations (cost nums[(i-k+n)%n]). Naturally, we'd pick the cheapest option available up to k rotations. We calculate this minimum cost for each of the n types, sum them up, and add the initial k * x rotation cost. By doing this for every possible k from 0 to n-1 and taking the minimum of all total costs, we find the global minimum cost.
class Solution { public long minCost(int[] nums, int x) { int n = nums.length; long minTotalCost = Long.MAX_VALUE; // k is the number of rotations for (int k = 0; k < n; k++) { long currentRotationCost = (long) k * x; long currentChocolatesCost = 0; // i is the type of chocolate for (int i = 0; i < n; i++) { long minCostForTypeI = (long) nums[i]; // j is the number of rotations when we buy chocolate i for (int j = 1; j <= k; j++) { minCostForTypeI = Math.min(minCostForTypeI, (long) nums[(i - j + n) % n]); } currentChocolatesCost += minCostForTypeI; } long currentTotalCost = currentRotationCost + currentChocolatesCost; minTotalCost = Math.min(minTotalCost, currentTotalCost); } return minTotalCost; }}Complexity
Time
O(n^3). There are three nested loops. The outer loop for `k` runs `n` times. The second loop for `i` runs `n` times. The innermost loop for `j` runs up to `n` times. This results in a cubic time complexity.
Space
O(1) extra space. We only use a few variables to keep track of costs, independent of the input size `n`.
Trade-offs
Pros
It is a straightforward implementation of the problem statement.
It requires no extra space apart from a few variables for calculation.
Cons
The
O(n^3)time complexity makes it too slow for the given constraints, likely resulting in a 'Time Limit Exceeded' error on larger test cases.
Solutions
Solution
class Solution {public long minCost(int[] nums, int x) { int n = nums.length; int[][] f = new int[n][n]; for (int i = 0; i < n; ++i) { f[i][0] = nums[i]; for (int j = 1; j < n; ++j) { f[i][j] = Math.min(f[i][j - 1], nums[(i - j + n) % n]); } } long ans = 1L << 60; for (int j = 0; j < n; ++j) { long cost = 1L * x * j; for (int i = 0; i < n; ++i) { cost += f[i][j]; } ans = Math.min(ans, cost); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.