Chocolate Distribution Problem: Codes with Visualization
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
Problem Statement
We have an array of chocolate packets where each value represents the number of chocolates in a packet. We need to distribute these packets to a given number of students such that:
- Each student gets exactly one packet
- The difference between the maximum and minimum number of chocolates given to students is minimized
For example, if we have chocolate packets with [7, 3, 2, 4, 9, 12, 56] and 3 students, we want to find the distribution that creates the smallest difference between the student who gets the most chocolates and the student who gets the fewest.
Brute Force Approach
Explanation
The brute force approach examines all possible ways to select 'm' packets from 'n' packets (where 'm' is the number of students). We:
- Generate all possible combinations of 'm' packets from 'n' packets
- For each combination, find the difference between maximum and minimum values
- Track the smallest difference found
This approach guarantees the correct answer but is computationally expensive as it needs to check every possible selection.
Time Complexity: O(n^m) where n is the number of packets and m is the number of students
Space Complexity: O(m) for storing the current combination
Python
from itertools import combinations
def find_min_difference(arr, m):
# If there are fewer packets than students or no packets/students
if m == 0 or len(arr) == 0 or len(arr) < m:
return 0
# Generate all possible m-sized combinations
min_diff = float('inf')
# Using itertools.combinations to get all possible selections
for combo in combinations(arr, m):
# Find difference between max and min in this selection
current_diff = max(combo) - min(combo)
min_diff = min(min_diff, current_diff)
return min_diff
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <functional>
using namespace std;
int findMinDifference(vector<int>& arr, int m) {
int n = arr.size();
// If there are fewer packets than students or no packets/students
if (m == 0 || n == 0 || n < m)
return 0;
int min_diff = INT_MAX;
vector<int> current;
function<void(int, int)> findCombinations = [&](int start, int count) {
if (count == m) {
int curr_max = *max_element(current.begin(), current.end());
int curr_min = *min_element(current.begin(), current.end());
min_diff = min(min_diff, curr_max - curr_min);
return;
}
if (start >= n || n - start < m - count)
return;
current.push_back(arr[start]);
findCombinations(start + 1, count + 1);
current.pop_back();
findCombinations(start + 1, count);
};
findCombinations(0, 0);
return min_diff;
}
Java
import java.util.*;
public class ChocolateDistribution {
static int min_diff = Integer.MAX_VALUE;
public static int findMinDifference(int[] arr, int m) {
if (m == 0 || arr.length == 0 || arr.length < m)
return 0;
min_diff = Integer.MAX_VALUE;
ArrayList<Integer> current = new ArrayList<>();
findCombinations(arr, m, 0, 0, current);
return min_diff;
}
private static void findCombinations(int[] arr, int m, int start, int count, ArrayList<Integer> current) {
if (count == m) {
int curr_max = Collections.max(current);
int curr_min = Collections.min(current);
min_diff = Math.min(min_diff, curr_max - curr_min);
return;
}
if (start >= arr.length || arr.length - start < m - count)
return;
current.add(arr[start]);
findCombinations(arr, m, start + 1, count + 1, current);
current.remove(current.size() - 1);
findCombinations(arr, m, start + 1, count, current);
}
}
Optimized Approach
Explanation
The key insight for optimization is that to minimize the difference between maximum and minimum values, we should pick consecutive elements from a sorted array.
Here's why the optimized approach works:
- Sort the array of chocolate packets
- Create a sliding window of size 'm' (number of students)
- For each possible window, calculate the difference between max and min values
- Track the smallest difference found
By sorting first, we ensure that any window of 'm' consecutive elements will have its minimum at the start and maximum at the end, making calculations simpler.
Time Complexity: O(n log n) where n is the number of packets (dominated by sorting)
Space Complexity: O(1) if we sort the array in-place, or O(n) otherwise
Consider the array [7 3 2 4 9 12 56] and m==3
First we sort the array
We consider all contiguous subarrays (windows) of size 3:
Window 1: [2, 3, 4]
- current_diff = 4 - 2 = 2
- min_diff = min(∞, 2) = 2
Window 2: [3, 4, 7]
- current_diff = 7 - 3 = 4
- min_diff = min(2, 4) = 2
Window 3: [4, 7, 9]
- current_diff = 9 - 4 = 5
- min_diff = min(2, 5) = 2
Window 4: [7, 9, 12]
- current_diff = 12 - 7 = 5
- min_diff = min(2, 5) = 2
Window 5: [9, 12, 56]
- current_diff = 56 - 9 = 47
- min_diff = min(2, 47) = 2
Chocolate Distribution Problem Visualization
<visualization-box>
Python
def find_min_difference(arr, m):
# If there are fewer packets than students or no packets/students
n = len(arr)
if m == 0 or n == 0 or n < m:
return 0
# Sort the array
arr.sort()
# Initialize minimum difference to a large value
min_diff = float('inf')
# Slide a window of size m through the sorted array
for i in range(n - m + 1):
current_diff = arr[i + m - 1] - arr[i]
min_diff = min(min_diff, current_diff)
return min_diff
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int findMinDifference(vector<int>& arr, int m) {
int n = arr.size();
// If there are fewer packets than students or no packets/students
if (m == 0 || n == 0 || n < m)
return 0;
// Sort the array
sort(arr.begin(), arr.end());
// Initialize minimum difference to a large value
int min_diff = INT_MAX;
// Slide a window of size m through the sorted array
for (int i = 0; i <= n - m; i++) {
int current_diff = arr[i + m - 1] - arr[i];
min_diff = min(min_diff, current_diff);
}
return min_diff;
}
Java
import java.util.Arrays;
public class ChocolateDistribution {
public static int findMinDifference(int[] arr, int m) {
int n = arr.length;
// If there are fewer packets than students or no packets/students
if (m == 0 || n == 0 || n < m)
return 0;
// Sort the array
Arrays.sort(arr);
// Initialize minimum difference to a large value
int min_diff = Integer.MAX_VALUE;
// Slide a window of size m through the sorted array
for (int i = 0; i <= n - m; i++) {
int current_diff = arr[i + m - 1] - arr[i];
min_diff = Math.min(min_diff, current_diff);
}
return min_diff;
}
}
Conclusion
1. The Chocolate Distribution Problem is a classic example that highlights how a smart use of sorting can drastically simplify a problem. Instead of checking every possible combination (which quickly becomes inefficient), we first sort the array and then scan through it with a fixed-size window. This approach not only reduces complexity but also brings clarity to the problem
2. sorting lays the groundwork for many optimized solutions. Especially in scenarios where we're dealing with differences — like minimizing the gap between the largest and smallest elements — a sorted structure turns a messy problem into a manageable one.
3. So next time you’re tackling a problem involving ranges, gaps, or distributions, ask yourself:"Can sorting help here?"Chances are, it just might lead you straight to an elegant solution.
