Published: 15 Apr 2025 | Reading Time: 9 min read
Fair distribution is a recurring theme in both real-life and computational problems. Among such problems, the Chocolate Distribution Problem stands out as a classic example used to teach sorting, optimization, and greedy strategies in algorithms.
The idea is simple: you have a bunch of chocolate packets, and you need to share them with a group of kids as fairly as possible. Sounds easy, right? But there's more to this problem than you can imagine.
In this blog we will simplify the chocolate distribution problem with easy approaches. You are going to learn about the problem, how to solve it step-by-step, and show you both basic and optimized solutions, along with code examples, outputs, and the efficiency of each technique.
The Chocolate Distribution Problem can be defined as follows:
This problem teaches how to apply a greedy approach and is commonly asked in coding interviews to assess problem-solving skills.
To solve the Chocolate Distribution Problem, sort the array of chocolate packets and find the minimum difference between the maximum and minimum in every group of m packets.
Then, return the smallest of these differences as the most fair distribution.
Let's say we have five packets of chocolates: {8, 11, 7, 15, 2}.
All possible ways to distribute five packets of chocolates among three students are:
Now, among all these combinations, the smallest difference is 4 (from the group {8, 11, 7}). So that's our best way to distribute the chocolates in the fairest manner.
To solve the problem efficiently, we need to reduce the difference between the largest and smallest packets among the chosen m packets. The trick lies in sorting the array and then checking every subarray of size m to find the one with the minimum difference between the largest and smallest values.
Let's break down the step-by-step logic:
This greedy technique is both efficient and elegant.
In the naive approach, we try all possible combinations of m packets from the array and calculate the difference between the maximum and minimum in each combination.
This method is straightforward but inefficient, especially for larger arrays.
import java.util.*;
public class ChocolateDistribution {
// Naive approach to find minimum difference
public static int naiveChocolateDistribution(int[] arr, int m) {
if (m == 0 || arr.length < m) {
return 0;
}
int minDiff = Integer.MAX_VALUE;
// Generate all combinations of size m
int n = arr.length;
int[] combo = new int[m];
minDiff = findMinDifference(arr, n, m, 0, combo, 0, minDiff);
return minDiff;
}
// Recursive method to generate combinations
public static int findMinDifference(int[] arr, int n, int m, int index, int[] combo, int i, int minDiff) {
if (index == m) {
int max = combo[0], min = combo[0];
for (int val : combo) {
if (val > max) max = val;
if (val < min) min = val;
}
return Math.min(minDiff, max - min);
}
if (i >= n) return minDiff;
combo[index] = arr[i];
minDiff = findMinDifference(arr, n, m, index + 1, combo, i + 1, minDiff);
minDiff = findMinDifference(arr, n, m, index, combo, i + 1, minDiff);
return minDiff;
}
public static void main(String[] args) {
int[] arr = {7, 3, 2, 4, 9, 12, 56};
int m = 3;
int result = naiveChocolateDistribution(arr, m);
System.out.println("Minimum difference is " + result);
}
}
naiveChocolateDistribution(int[] arr, int m)
findMinDifference(...)
This is a recursive function that:
There are two recursive calls:
This helps explore all possible ways of selecting m packets.
main(String[] args)
The code checks every possible group of m packets, calculates the max-min difference for each, and returns the smallest difference among all combinations.
Minimum difference is 2
1. Time Complexity: O(nCm) or O(n^m)
This means the program checks all possible groups of m students from n chocolate packets. For example, if you have 7 packets and need to choose 3, there are many different combinations to consider. The more packets (n) you have and the more students (m) you need to distribute them to, the more combinations the code has to go through. As a result, the time taken increases very quickly when n or m becomes large. That's why this approach is simple but becomes slow and inefficient for larger inputs.
2. Space Complexity: O(1)
The code doesn't require much extra memory to run. It only uses a small temporary array to store each combination while checking. Apart from the original input array and this small combination array, no additional data structures or large memory allocations are needed.
This approach is not suitable for large inputs due to its exponential time complexity.
The efficient approach is built on the idea that sorting reduces the effort of evaluating differences. By scanning sorted segments of the array, we can quickly determine the smallest difference possible.
import java.util.Arrays;
public class ChocolateDistributionEfficient {
// Efficient method using sorting and sliding window
public static int efficientChocolateDistribution(int[] arr, int m) {
if (m == 0 || arr.length < m) {
return 0;
}
Arrays.sort(arr); // Step 1: Sort the array
int minDiff = Integer.MAX_VALUE;
// Step 2: Slide window of size m
for (int i = 0; i <= arr.length - m; i++) {
int currentDiff = arr[i + m - 1] - arr[i];
if (currentDiff < minDiff) {
minDiff = currentDiff;
}
}
return minDiff;
}
public static void main(String[] args) {
int[] arr = {7, 3, 2, 4, 9, 12, 56};
int m = 3;
int result = efficientChocolateDistribution(arr, m);
System.out.println("Minimum difference is " + result);
}
}
efficientChocolateDistribution Method
This function aims to find the minimum difference between the maximum and minimum number of chocolates in any group of m packets.
if (m == 0 || arr.length < m) {
return 0;
}
If m is 0 or the number of packets is less than m, it's not possible to distribute — return 0.
Arrays.sort(arr);
Sorting helps to line up packets with similar values next to each other, making it easier to find the smallest difference.
int minDiff = Integer.MAX_VALUE;
Start with the maximum possible value. We'll try to find a smaller one.
for (int i = 0; i <= arr.length - m; i++) {
int currentDiff = arr[i + m - 1] - arr[i];
if (currentDiff < minDiff) {
minDiff = currentDiff;
}
}
This loop checks every group of m continuous packets.
For each group, it calculates the difference between the largest and smallest chocolates.
It updates minDiff whenever a smaller difference is found.
return minDiff;
main Method
This part sets up and runs the program.
int[] arr = {7, 3, 2, 4, 9, 12, 56};
int m = 3;
int result = efficientChocolateDistribution(arr, m);
System.out.println("Minimum difference is " + result);
Minimum difference is 2
Time Complexity
The array is sorted first, and sorting takes time based on its size, roughly O(n log n). This is the most time-consuming part, but it's still much faster than checking all possible combinations.
Space Complexity
The program only uses a few variables to track values like the minimum difference, so it doesn't take any extra space, and we call this O(1) space.
Given an array where each element represents the number of chocolates in a packet, and a number m representing the number of students, the objective is to distribute the packets among the students such that:
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
// Function to get the smallest difference between the highest and lowest chocolates in any valid group
int getMinimumChocolateGap(std::vector<int>& packets, int numStudents) {
int totalPackets = packets.size();
// Return 0 if distribution isn't possible
if (numStudents == 0 || totalPackets < numStudents)
return 0;
// Sort packets to simplify finding smallest range
std::sort(packets.begin(), packets.end());
int smallestGap = INT_MAX;
// Slide through sorted packets to find the group with minimum difference
for (int start = 0; start <= totalPackets - numStudents; ++start) {
int end = start + numStudents - 1;
int currentGap = packets[end] - packets[start];
if (currentGap < smallestGap) {
smallestGap = currentGap;
}
}
return smallestGap;
}
int main() {
std::vector<int> packetChocolates = {7, 3, 2, 4, 9, 12, 56};
int students = 3;
int answer = getMinimumChocolateGap(packetChocolates, students);
std::cout << "Minimum difference is: " << answer << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
int getMinimumChocolateGap(std::vector<int>& packets, int numStudents)
if (numStudents == 0 || totalPackets < numStudents)
return 0;
std::sort(packets.begin(), packets.end());
int smallestGap = INT_MAX;
for (int start = 0; start <= totalPackets - numStudents; ++start)
int end = start + numStudents - 1;
int currentGap = packets[end] - packets[start];
if (currentGap < smallestGap)
smallestGap = currentGap;
return smallestGap;
std::vector<int> packetChocolates = {7, 3, 2, 4, 9, 12, 56};
int students = 3;
int answer = getMinimumChocolateGap(packetChocolates, students);
std::cout << "Minimum difference is: " << answer << std::endl;
Minimum difference is: 2
Sorting the array takes O(n log n), where n is the number of packets. The subsequent traversal of the array to find the minimum difference takes O(n). Thus, the overall time complexity is O(n log n).
The algorithm operates in O(1) additional space, meaning it doesn't require extra space proportional to the input size, making it efficient in terms of memory usage.
The objective is to distribute the chocolate packets among the students in such a way that the difference between the packet with the highest and the packet with the lowest number of chocolates is as small as possible. The packets may contain varying amounts of chocolates.
You need to find the minimum difference between the chocolates in the packets given to any two students.
arr = [12, 4, 7, 9, 2, 23, 25, 41, 40, 40, 48, 16, 26]
m = 5
The minimum difference is 10.
def chocolate_distribution(arr, m):
# Check for edge case where distribution is not possible
if m == 0 or len(arr) < m:
return 0
# Sort the array of chocolate packets
arr.sort()
# Initialize the minimum difference to a large value
min_diff = float('inf')
# Use a sliding window of size m to calculate the minimum difference
for i in range(len(arr) - m + 1):
current_diff = arr[i + m - 1] - arr[i] # difference between largest and smallest
min_diff = min(min_diff, current_diff)
return min_diff
# Example usage
arr = [12, 4, 7, 9, 2, 23, 25, 41, 40, 40, 48, 16, 26]
m = 5
result = chocolate_distribution(arr, m)
print(f"The minimum difference is {result}")
1. Function Definition: The function chocolate_distribution takes two inputs:
2. Edge Case Handling: The first check ensures that if m is 0 (meaning no students) or the length of the arr is less than m (meaning there aren't enough packets to give each student one), the function returns 0. This is because distributing chocolates is not possible in these cases.
3. Sorting: The array arr is sorted in non-decreasing order. Sorting helps in minimizing the difference between the largest and smallest chocolates in any selected group of m packets. When sorted, the chocolates that are closer in size will be adjacent to each other.
4. Initialize min_diff: The variable min_diff is initialized to infinity (float('inf')), representing an initially large value. This will be used to store the minimum difference between the largest and smallest chocolate counts as we check different subarrays.
5. Sliding Window: The code uses a sliding window technique:
6. Returning the Result: After checking all possible windows (subarrays of size m), the function returns the smallest difference (min_diff), which is the optimal way of distributing chocolates among the students such that the difference between the maximum and minimum chocolates is minimized.
7. Example Usage: The example provided uses an array of chocolate packets (arr = [12, 4, 7, 9, 2, 23, 25, 41, 40, 40, 48, 16, 26]) and sets m = 5 (i.e., distributing chocolates to 5 students).
The minimum difference is 10.
1. Encourages Logical Thinking
Helps learners understand how to minimize the difference in a given dataset — a common real-world need.
2. Teaches Sorting and Sliding Window Techniques
Introduces efficient techniques like sorting and using a sliding window to find optimal subarrays.
3. Real-life Relevance
Can be applied to resource allocation problems where fair distribution is needed (e.g., workload balancing, ration distribution).
4. Simplifies a Complex Concept
Provides an easy-to-understand setup for learners while teaching a more complex concept of optimization.
5. Interview Favorite
A classic data structures and algorithms problem, often asked in interviews, making it good for practice.
1. Assumes Fixed Packet Sizes
In real life, you might be able to split resources, unlike in this problem, where you must assign whole packets only.
2. Ignores Packet Quantity Limitations
It assumes there's a sufficient number of packets to give one to each student, not always realistic.
3. No Student Preferences Considered
Doesn't account for individual needs or preferences, which is often important in real-world distributions.
4. Static Approach
It's a one-time allocation; dynamic or real-time allocation scenarios aren't handled.
5. Over-Simplified Model
While it's great for beginners, the model is too simple for solving more complex optimization or equitable distribution problems.
The Chocolate Distribution Problem, while deceptively simple, offers a rich learning ground for understanding greedy algorithms and optimization. From a brute-force naive approach to an efficient window-sliding technique, the journey of solving this problem is a microcosm of real-world algorithm design: start simple, then optimize.
By mastering this problem, you're not just solving a theoretical challenge; you are preparing for scenarios in system design, resource allocation, and even real-life dilemmas that demand fairness and efficiency.
To minimize the difference between the maximum and minimum chocolates distributed to students. Each student must get exactly one packet.
Sort the array of packets and use a sliding window of size equal to the number of students. Identify which window has the smallest difference between the preceding and final components.
The time complexity is O(N log N) due to sorting, where N is the number of packets. Sliding the window takes linear time, i.e., O(N).
No, sorting is essential to efficiently find the minimal difference window. Without sorting, it would require checking all combinations, leading to high time complexity.
It's an invalid input case; each student must receive one packet. Hence, the number of students should be ≤ number of packets.
Source: NxtWave - CCBP Blog