Collecting Chocolates

MEDIUM

Description

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 i^th type.

In one operation, you can do the following with an incurred cost of x:

Simultaneously change the chocolate of i^th type to ((i + 1) mod n)^th type 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 1^st 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 2^ndtype 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 0^thtype 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 <= 1000
1 <= nums[i] <= 10⁹
1 <= x <= 10⁹

Approaches

Checkout 2 different approaches to solve Collecting Chocolates. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

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 minTotalCost to a very large value to store the minimum cost found.
Iterate through all possible numbers of rotations, k, from 0 to n-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 type i from 0 to n-1, find its minimum possible acquisition cost. This involves checking its cost at 0, 1, ..., k rotations. c. The cost of type i after j rotations is nums[(i - j + n) % n]. Find the minimum of these values for j in [0, k]. d. Add this minimum cost for type i to a running sum for the current k.
After summing the minimum costs for all types, add the rotation cost k * x to get the total cost for k rotations.
Update minTotalCost = min(minTotalCost, currentTotalCost).
After checking all k from 0 to n-1, minTotalCost will hold the answer.

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 Analysis

Time Complexity: 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 Complexity: O(1) extra space. We only use a few variables to keep track of costs, independent of the input size `n`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Collecting Chocolates. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Collecting Chocolates

Patterns:

Enumeration

Data Structures:

Array

Companies:

Deutsche Bank |