Collecting Chocolates — Solution in Python, Java & C++
Collecting Chocolates solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.
Collecting Chocolates is a medium coding problem on arrays and enumeration, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Enumeration
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A shop has n chocolates in a row. At the start, the chocolate at index i is of type i, and buying the chocolate at index i costs nums[i] — the price belongs to the position, not the type.
You may perform an operation any number of times, each costing x: every chocolate changes type at once, the one of type t becoming type (t + 1) mod n.
You want to own one chocolate of every type. You can interleave purchases and operations freely. Return the minimum total cost (purchases plus operations).
The constraints are tightened from the original so the answer always fits in a 32-bit integer.
Example 1
Input: nums = [20,1,15], x = 5
Output: 13
Explanation: Buy type 1 for 1. Rotate (cost 5): index 1 now holds type 2 — buy it for 1. Rotate again (cost 5): index 1 holds type 0 — buy it for 1. Total 1 + 5 + 1 + 5 + 1 = 13.
Example 2
Input: nums = [1,2,3], x = 4
Output: 6
Explanation: Rotating never pays off: buy each type where it starts, for 1 + 2 + 3 = 6.
Example 3
Input: nums = [7], x = 1000000
Output: 7
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 10^61 <= x <= 10^6
Hints for Collecting Chocolates
Hint 1
Fix the number of operations
kyou will do in total. Doing more thann - 1can never help — afternthe types are back where they started.Hint 2
With
koperations, typetpasses throughk + 1consecutive positions, and you can buy it at whichever of them is cheapest. The cost isk * xplus the sum of those minima.Hint 3
Going from
ktok + 1extends every type's window by one position, so update each type's running minimum inO(1)instead of recomputing it:O(n^2)overall.
How to solve Collecting Chocolates
Choose the total number of rotations k (0 <= k < n). Then every type can be bought at the cheapest of the k + 1 positions it visits, and those purchases can always be scheduled at the right moments. Try every k, extending each type's window by one per step.
Approach
- Let
best[i] = nums[i]— the cheapest price for the type that starts atiwith zero rotations — andanswer = sum(best). - For
k = 1 .. n - 1: setbest[i] = min(best[i], nums[(i + k) mod n])for everyi, thenanswer = min(answer, k * x + sum(best)). - Return
answer.
Why it works
With k rotations each type occupies k + 1 cyclically consecutive positions at successive moments and can be bought at any one of them, so the cheapest of those prices is optimal for it independently of the other types. Summing over all types, the windows starting at each index and the windows ending at each index are the same set, so best as computed gives the same total. Doing k >= n rotations costs more and opens no new positions, so the enumeration over 0 <= k < n covers the optimum.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
k * x + sum(best)can exceed2^31 - 1even though the answer does not (it is at mostsum(nums)): use 64-bit arithmetic for the candidate.- Do not stop at the first
kwhere the cost rises — try everykup ton - 1.
Reference solution
Python
from typing import List
def minCost(nums: List[int], x: int) -> int:
n = len(nums)
best = nums[:]
answer = sum(best)
for k in range(1, n):
for i in range(n):
v = nums[(i + k) % n]
if v < best[i]:
best[i] = v
answer = min(answer, k * x + sum(best))
return answerJava
public static int minCost(int[] nums, int x) {
int n = nums.length;
int[] best = nums.clone();
long answer = 0;
for (int v : best) answer += v;
for (int k = 1; k < n; k++) {
long total = (long) k * x;
for (int j = 0; j < n; j++) {
best[j] = Math.min(best[j], nums[(j + k) % n]);
total += best[j];
}
answer = Math.min(answer, total);
}
return (int) answer;
}C++
int minCost(vector<int>& nums, int x) {
int n = nums.size();
vector<int> best(nums);
long long answer = 0;
for (int v : best) answer += v;
for (int k = 1; k < n; k++) {
long long total = (long long) k * x;
for (int j = 0; j < n; j++) {
best[j] = min(best[j], nums[(j + k) % n]);
total += best[j];
}
answer = min(answer, total);
}
return (int) answer;
}JavaScript
var minCost = function(nums, x) {
var n = nums.length;
var best = nums.slice();
var answer = 0;
for (var i = 0; i < n; i++) answer += best[i];
for (var k = 1; k < n; k++) {
var total = k * x;
for (var j = 0; j < n; j++) {
var v = nums[(j + k) % n];
if (v < best[j]) best[j] = v;
total += best[j];
}
if (total < answer) answer = total;
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays