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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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^9
  • 1 <= x <= 10^9

Solution

Method 1 – Enumerate Rotations (Sliding Minimum)

Intuition

Since each operation rotates the types, we can try all possible numbers of operations (from 0 to n-1). For each rotation, we can keep track of the minimum cost to collect each type so far. The answer is the minimum total cost over all rotations.

Approach

  1. Let n be the length of nums.
  2. For each rotation k from 0 to n-1:
    • For each type, update the minimum cost to collect that type after k rotations.
    • Compute the total cost as the sum of minimum costs for all types plus k * x (the cost of rotations).
    • Track the minimum total cost.
  3. Return the minimum total cost found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    long long minCost(vector<int>& nums, int x) {
        int n = nums.size();
        vector<long long> minCost(nums.begin(), nums.end());
        long long ans = accumulate(minCost.begin(), minCost.end(), 0LL);
        for (int k = 1; k < n; ++k) {
            for (int i = 0; i < n; ++i)
                minCost[i] = min(minCost[i], (long long)nums[(i + k) % n]);
            long long total = accumulate(minCost.begin(), minCost.end(), 0LL) + (long long)k * x;
            ans = min(ans, total);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func minCost(nums []int, x int) int64 {
    n := len(nums)
    minCost := make([]int, n)
    copy(minCost, nums)
    ans := int64(0)
    for _, v := range minCost {
        ans += int64(v)
    }
    for k := 1; k < n; k++ {
        for i := 0; i < n; i++ {
            if nums[(i+k)%n] < minCost[i] {
                minCost[i] = nums[(i+k)%n]
            }
        }
        total := int64(k) * int64(x)
        for _, v := range minCost {
            total += int64(v)
        }
        if total < ans {
            ans = total
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        long[] minCost = new long[n];
        for (int i = 0; i < n; i++) minCost[i] = nums[i];
        long ans = 0;
        for (long v : minCost) ans += v;
        for (int k = 1; k < n; k++) {
            for (int i = 0; i < n; i++)
                minCost[i] = Math.min(minCost[i], nums[(i + k) % n]);
            long total = (long)k * x;
            for (long v : minCost) total += v;
            ans = Math.min(ans, total);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minCost(nums: IntArray, x: Int): Long {
        val n = nums.size
        val minCost = LongArray(n) { nums[it].toLong() }
        var ans = minCost.sum()
        for (k in 1 until n) {
            for (i in 0 until n) {
                minCost[i] = minOf(minCost[i], nums[(i + k) % n].toLong())
            }
            val total = minCost.sum() + k.toLong() * x
            ans = minOf(ans, total)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def minCost(self, nums: list[int], x: int) -> int:
        n = len(nums)
        min_cost = nums[:]
        ans = sum(min_cost)
        for k in range(1, n):
            for i in range(n):
                min_cost[i] = min(min_cost[i], nums[(i + k) % n])
            total = sum(min_cost) + k * x
            ans = min(ans, total)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn min_cost(nums: Vec<i32>, x: i32) -> i64 {
        let n = nums.len();
        let mut min_cost: Vec<i64> = nums.iter().map(|&v| v as i64).collect();
        let mut ans: i64 = min_cost.iter().sum();
        for k in 1..n {
            for i in 0..n {
                min_cost[i] = min_cost[i].min(nums[(i + k) % n] as i64);
            }
            let total: i64 = min_cost.iter().sum::<i64>() + (k as i64) * (x as i64);
            ans = ans.min(total);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    minCost(nums: number[], x: number): number {
        const n = nums.length;
        let minCost = nums.slice();
        let ans = minCost.reduce((a, b) => a + b, 0);
        for (let k = 1; k < n; k++) {
            for (let i = 0; i < n; i++) {
                minCost[i] = Math.min(minCost[i], nums[(i + k) % n]);
            }
            const total = minCost.reduce((a, b) => a + b, 0) + k * x;
            ans = Math.min(ans, total);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)