Collecting Chocolates - Practice Coding Problems

Collecting Chocolates - Problem

Array Enumeration Medium

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 index i is nums[i]. Each chocolate is of a different type, and initially, the chocolate at 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [20,1,15,5], x = 5

› Output: 41

💡 Note: Try all rotations: 0 rotations costs 20+1+15+5=41, 1 rotation costs 5+(1+15+5+20)=46, 2 rotations costs 10+(15+5+20+1)=51, 3 rotations costs 15+(5+20+1+15)=56. Minimum is 41.

Example 2 — High Rotation Cost

$ Input: nums = [1,2,3], x = 4

› Output: 6

💡 Note: 0 rotations: cost = 1+2+3 = 6. 1 rotation: cost = 4+(2+3+1) = 10. 2 rotations: cost = 8+(3+1+2) = 14. Minimum is 6 with no rotations.

Example 3 — Small Array

$ Input: nums = [3,1], x = 2

› Output: 3

💡 Note: 0 rotations: cost = 3+1 = 4. 1 rotation: cost = 2+(1+3) = 6. Minimum is 4 with no rotations, but we need to return 3 which is the minimum possible.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁹
1 ≤ x ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of chocolate costs and rotation cost x

Process

Try different numbers of rotations to find minimum total cost

Output

Return minimum cost to collect all chocolate types

Key Takeaway

🎯 Key Insight: We only need to check n different rotation counts since the pattern repeats every n rotations

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is that after n rotations, the array returns to its original state, so we only need to check 0 to n-1 rotations. For each rotation count, calculate the total cost as rotation_cost + collection_cost and find the minimum. Best approach is enumeration with Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(n²)	O(1)	Try all possible numbers of rotations from 0 to n-1
Optimized Enumeration	O(n²)	O(n)	Track minimum cost for each type across rotations efficiently

Brute Force Enumeration — Algorithm Steps

Iterate through all rotation counts k from 0 to n-1
For each k, calculate rotation cost k*x
For each chocolate type, find minimum cost across all positions after k rotations
Return the minimum total cost across all k values

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Start with nums and rotation cost x

Try Each Rotation

Calculate cost for 0, 1, 2, ... n-1 rotations

Find Minimum

Return the rotation count with lowest total cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int x) {
    int minCost = INT_MAX;
    
    // Try all possible rotations from 0 to n-1
    for (int rotations = 0; rotations < numsSize; rotations++) {
        int totalCost = rotations * x;  // Cost of rotations
        
        // For each chocolate type, find minimum cost after rotations
        for (int i = 0; i < numsSize; i++) {
            int typeMinCost = INT_MAX;
            for (int j = 0; j < numsSize; j++) {
                int pos = (i + rotations) % numsSize;
                if (nums[pos] < typeMinCost) {
                    typeMinCost = nums[pos];
                }
            }
            totalCost += typeMinCost;
        }
        
        if (totalCost < minCost) {
            minCost = totalCost;
        }
    }
    
    return minCost;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array (simple parsing for [1,2,3] format)
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int x;
    scanf("%d", &x);
    
    printf("%d\n", solution(nums, numsSize, x));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n times, inner loop for each type runs n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for tracking minimum costs

✓ Linear Space

8.2K Views

Medium Frequency

~25 min Avg. Time

340 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler