Collecting Chocolates

Medium
1841.

Collecting Chocolates

Collecting Chocolates is a medium coding problem on arrays and enumeration, asked in Amazon interviews.

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 <= 1000
  • 1 <= nums[i] <= 10^6
  • 1 <= x <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minCost = function(nums, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • 1 <= nums[i] <= 10^6
  • 1 <= x <= 10^6

Hints for Collecting Chocolates

  1. Hint 1

    Fix the number of operations k you will do in total. Doing more than n - 1 can never help — after n the types are back where they started.

  2. Hint 2

    With k operations, type t passes through k + 1 consecutive positions, and you can buy it at whichever of them is cheapest. The cost is k * x plus the sum of those minima.

  3. Hint 3

    Going from k to k + 1 extends every type's window by one position, so update each type's running minimum in O(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

  1. Let best[i] = nums[i] — the cheapest price for the type that starts at i with zero rotations — and answer = sum(best).
  2. For k = 1 .. n - 1: set best[i] = min(best[i], nums[(i + k) mod n]) for every i, then answer = min(answer, k * x + sum(best)).
  3. 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 exceed 2^31 - 1 even though the answer does not (it is at most sum(nums)): use 64-bit arithmetic for the candidate.
  • Do not stop at the first k where the cost rises — try every k up to n - 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 answer

Java

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