Skip to content

2735. Collecting Chocolates 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  long long minCost(vector<int>& nums, long long x) {
    const int n = nums.size();
    long ans = LONG_MAX;
    // minCost[i] := the minimum cost to collect the i-th type
    vector<int> minCost(n, INT_MAX);

    for (int rotate = 0; rotate < n; ++rotate) {
      for (int i = 0; i < n; ++i)
        minCost[i] = min(minCost[i], nums[(i - rotate + n) % n]);
      ans =
          min(ans, accumulate(minCost.begin(), minCost.end(), 0L) + rotate * x);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Solution {
  public long minCost(int[] nums, long x) {
    int n = nums.length;
    long ans = Long.MAX_VALUE;
    // minCost[i] := the minimum cost to collect the i-th type
    int[] minCost = new int[n];
    Arrays.fill(minCost, Integer.MAX_VALUE);

    for (int rotate = 0; rotate < n; ++rotate) {
      for (int i = 0; i < n; ++i)
        minCost[i] = Math.min(minCost[i], nums[(i - rotate + n) % n]);
      ans = Math.min(ans, Arrays.stream(minCost).asLongStream().sum() + rotate * x);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def minCost(self, nums: list[int], x: int) -> int:
    n = len(nums)
    ans = math.inf
    # minCost[i] := the minimum cost to collect the i-th type
    minCost = [math.inf] * n

    for rotate in range(n):
      for i in range(n):
        minCost[i] = min(minCost[i], nums[(i - rotate + n) % n])
      ans = min(ans, sum(minCost) + rotate * x)

    return ans