# Collecting Chocolates
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/collecting-chocolates)
Canonical: https://scaleengineer.com/dsa/problems/collecting-chocolates
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank)
---
## Problem
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 `ith` 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 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 <= 1000`
* `1 <= nums[i] <= 109`
* `1 <= x <= 109`

# Approaches
## 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.
**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`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Initialize a variable `minTotalCost` to a very large value to store the minimum cost found.
2. Iterate through all possible numbers of rotations, `k`, from `0` to `n-1`.
3. 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`.
4. After summing the minimum costs for all types, add the rotation cost `k * x` to get the total cost for `k` rotations.
5. Update `minTotalCost = min(minTotalCost, currentTotalCost)`.
6. After checking all `k` from `0` to `n-1`, `minTotalCost` will hold the answer.

## Optimized Iterative Approach
This approach improves upon the brute-force method by using a dynamic programming-like optimization. Instead of re-calculating the minimum cost for each chocolate type from scratch for every number of rotations, we maintain an array of the minimum costs found so far. As we consider an additional rotation (`k`), we can efficiently update these minimum costs by just comparing them with the new costs available after this `k`-th rotation.
**Time:** O(n^2). The outer loop for `k` runs `n` times. The inner loop to update and sum costs also runs `n` times. This results in a quadratic time complexity. · **Space:** O(n). We use an auxiliary array `minCostsSoFar` of size `n` to store the running minimum costs for each chocolate type.
**Pros:** Significantly more efficient than the brute-force approach with `O(n^2)` complexity.; Optimal for the given constraints and passes all test cases.
**Cons:** Requires O(n) extra space to store the minimum costs for each chocolate type.
### Explanation
We can observe that the calculation in the brute-force approach is highly redundant. The minimum cost for a type `i` with `k` rotations is simply the minimum of its cost with `k-1` rotations and its cost at exactly `k` rotations. This suggests an iterative solution.

We can iterate through the number of rotations `k` from 0 to `n-1`. We'll use an auxiliary array, `minCostsSoFar`, of size `n`, where `minCostsSoFar[i]` stores the minimum cost to acquire chocolate of type `i` considering all rotations from 0 up to the current `k`.

- For `k=0`, `minCostsSoFar` is just a copy of the `nums` array. The total cost is the sum of these costs.
- For `k=1`, we update each `minCostsSoFar[i]` by comparing its current value with the cost of type `i` after 1 rotation, which is `nums[(i-1+n)%n]`. We then compute the new total cost: `(1 * x) + sum(minCostsSoFar)`.
- We continue this process for `k` up to `n-1`. In each step `k`, we update `minCostsSoFar[i]` with `min(minCostsSoFar[i], nums[(i-k+n)%n])` and recalculate the total cost. The overall minimum of these total costs is the answer.

This avoids the innermost loop of the brute-force approach, reducing the complexity from cubic to quadratic.

```java
class Solution {
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        // minCostsSoFar[i] stores the minimum cost to collect chocolate of type i
        // considering all rotations from 0 up to the current k.
        long[] minCostsSoFar = new long[n];
        for (int i = 0; i < n; i++) {
            minCostsSoFar[i] = nums[i];
        }

        long minTotalCost = 0;
        for (long cost : minCostsSoFar) {
            minTotalCost += cost;
        }

        // k is the number of rotations
        for (int k = 1; k < n; k++) {
            long currentChocolatesCost = 0;
            // i is the type of chocolate
            for (int i = 0; i < n; i++) {
                // Cost of type 'i' after 'k' rotations is nums[(i - k + n) % n]
                long costAfterKRotations = (long) nums[(i - k + n) % n];
                minCostsSoFar[i] = Math.min(minCostsSoFar[i], costAfterKRotations);
                currentChocolatesCost += minCostsSoFar[i];
            }
            
            long currentTotalCost = (long) k * x + currentChocolatesCost;
            minTotalCost = Math.min(minTotalCost, currentTotalCost);
        }

        return minTotalCost;
    }
}
```
### Algorithm
1. Initialize an array `minCostsSoFar` of size `n` with the initial costs from `nums`. This represents the minimum costs for `k=0` rotations.
2. Calculate the initial total cost by summing up `minCostsSoFar` and store it in `minTotalCost`.
3. Iterate `k` from `1` to `n-1`, representing the number of rotations.
4. In each iteration `k`:
    a. Calculate the rotation cost: `rotationCost = (long)k * x`.
    b. Initialize `currentChocolatesCost = 0`.
    c. Iterate through each chocolate type `i` from `0` to `n-1`:
        i. The cost of type `i` after `k` rotations is `nums[(i - k + n) % n]`.
        ii. Update the minimum cost for type `i`: `minCostsSoFar[i] = min(minCostsSoFar[i], new_cost)`.
        iii. Add the updated `minCostsSoFar[i]` to `currentChocolatesCost`.
    d. Calculate the total cost for `k` rotations: `totalCostForK = rotationCost + currentChocolatesCost`.
    e. Update the overall minimum: `minTotalCost = min(minTotalCost, totalCostForK)`.
5. Return `minTotalCost`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
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))

```

### CPP

```cpp
class Solution {
public:
  long long minCost(vector<int> &nums, int x) {
    int n = nums.size();
    int f[n][n];
    for (int i = 0; i < n; ++i) {
      f[i][0] = nums[i];
      for (int j = 1; j < n; ++j) {
        f[i][j] = min(f[i][j - 1], nums[(i - j + n) % n]);
      }
    }
    long long ans = 1LL << 60;
    for (int j = 0; j < n; ++j) {
      long long cost = 1LL * x * j;
      for (int i = 0; i < n; ++i) {
        cost += f[i][j];
      }
      ans = min(ans, cost);
    }
    return ans;
  }
};

```