Chocolate Distribution Problem is a very famous problem in Data Structures and Algorithm. Solving the Chocolate Distribution Problem, we face a mind-boggling problem of algorithmic calculations which not only can serve as a base in mathematics but can be used in many different areas. The task consists of the array of chocolates in the packing and the number of children, which is to be reduced to the maximum difference between the number of chocolates given to the children. In this blog, we will see two approaches to solve the problem:
Understanding the Chocolate Distribution Problem
For instance, the number of chocolates in the packets we have can be shown by an array, and we are trying to divide this number of chocolates into a group of students. The goal is to make sure that every student gets one pack, there is no difference regarding the number of chocolates they will receive, and to make the whole distribution process as fair as possible.
Example Scenario: Take a basket of chocolate packets: {3, 4, 1, 9, 56,7, 9, 12}, and involve 5 students for distribution. The objective is to submit an answer that minimizes the difference between the number of chocolates received by the minimum and maximum number of students.
- Input: arr[] = {3, 4, 1, 9, 56, 7, 9, 12}, m = 5
- Output: Minimum Difference is 6
- Explanation:
- If packets {3, 4, 1, 7, 9} are distributed among 5 children, the difference is 9 - 1 = 8.
- If packets {3, 4, 7, 9, 9} are distributed, the difference is 9 - 3 = 6 (minimum).
- If packets {4, 7, 9, 9, 12} are distributed, the difference is 12 - 4 = 8.
- If packets {7, 9, 9, 12, 56} are distributed, the difference is 56 - 7 = 49.
- Hence, the minimum difference between maximum and minimum chocolates is 6 by choosing packets: {3, 4, 1, 7, 9}.
- 1 ≤ N ≤ 10^5
- 1 ≤ Ai ≤ 10^9
- 1 ≤ M ≤ N
Approach 1: Brute Force
The use of brute force in chocolate distribution problem means checking all possible subsets of length m ( number of kids) from the give array of chocolate packets.
Intuition: The brute-force approach is based on the custom of looking at all possible combinations of elements of length m in the given array and then select this subset, which has the lowest difference between the values and highest values.
Algorithm: Below is the brute force algorithm for a chocolate distribution problem:
1. Define a 2D array that is of (2D) type and has a length m, to hold all the sets of length m.
2. The recursive method finds all possible subsets from the given array and its size m.
3. Make a recursive function that can call itself and accept array, index of elements (starting from zero), a 2D ArrayList to contain subset elements and a 1D ArrayList to store the current subset, and m (size of the subset) as parameters.
4. Inside of recursive function, appropriate base case and recursive steps should be described.
Recursive Steps:
• Include the current element in the subset: Invoke the function with the next argument, add the element to a 1D ArrayList, then repeat the same procedure.
• Exclude the current element from the subset: Jump to the next index number of the set without the new element in the subset.
//Include the element in our subset
store the element inside the 1D ArrayList.
recursiveFunction(array, index+1, 2D ArryaList, 1D ArrayList, m);
remove the last visited element from the 1D ArrayList.
//Exclude the element in our subset
recursiveFunction(array, index+1, 2D ArryaList, 1D ArrayList, m);
Explanation:
This set of a array can happen by getting elements from an original array, either by including every selection of an element, or excluding every one of them.
• In a case that a specific element of the subset needs to be added, then it will be added to the 1D array list and we will wait for the next element on the list.
• The activity consisting of erasing an element from the subset is as simple as the next index which isn’t to include in the subset.
We make sure that each and every combination of elements explored using recursion is done.
Base Case:
if(index == array's length){
if(1D ArrayList size == m){
Store the subset of 1D ArrayList inside the
2D ArrayList.
}
return;
}
Recursion will keep going on until the index is beyond the length of the array. At this point:
• If the length of the 1D ArrayList has reached m, we have generated an m-size subset.
• We store this whole subset in the 2D ArrayList called allSubsets that is used to hold all subsets of length m.
Once the subsets have been created, we enter the looping process of the two-dimensional list.
• We keep an integer variable answer = Integer.MAX_VALUE initialized to save the lowest among the highest and smallest values of each subset.
• Computing the greatest and smallest differences in each subset would be performed by iteration, with the answer variable being refreshed with the minimal difference encountered in the whole process.
In the end, we print the statement the answer variable, which stores the minimum difference between the number of student who gets the maximum chocolates and the student who is given the minimum chocolates.
Code using Brute Approach
Java:
import java.util.;
public class Main {
//Recursive function to get all the
//Subsets of size m.
public static void subSet(int[] arr, int idx, List<List<Integer>> list, List<Integer> l, int m){
//Base Case
if(idx == arr.length){
if(l.size() == m ){
list.add(new ArrayList<>(l));
}
return;
}
//Including the element in subset
//Adding element in the 1D ArrayList
l.add(arr[idx]);
subSet(arr, idx+1, list, l, m);
//Removing element from the 1D ArrayList (BackTracking)
l.remove(l.size() - 1);
//Excluding the element
subSet(arr, idx+1, list, l, m);
}
//Minimum element from the subset
public static int findMin(List<Integer> l){
int min = Integer.MAX_VALUE;
for(int i : l){
min = Math.min(min, i);
}
return min;
}
//Maximum element from the subset
public static int findMax(List<Integer> l){
int max = Integer.MIN_VALUE;
for(int i : l){
max = Math.max(max, i);
}
return max;
}
//main function
public static void main(String args[]) {
//2D ArrayList to store all the subsets
List<List<Integer>> list = new ArrayList<>();
//1D ArrayList to store the perticular subset
List<Integer> l = new ArrayList<>();
// arr[0..n-1] represents sizes of packets
int[] arr = {3, 4, 1, 9, 56, 7, 9, 12};
//Number of students
int m = 5;
//Recursive function
subSet(arr, 0, list, l, m);
int ans = Integer.MAX_VALUE;
//Finding the minimum difference between
//Maximum and minimum values of
//Distribution.
for(List<Integer> i : list){
int min = findMin(i);
int max = findMax(i);
int diff = max - min;
ans = Math.min(ans, diff);
}
//Printing the minimum difference
System.out.println(ans);
}
}
Python:
def findMinDiff(A,N,M):
res = []
# Initializing our minimum difference
# to minus infinity
minimum_difference = float('inf')
# finding subset
def findSubset(A, path, idx):
if idx == N:
if len(path) == M:
res.append(path[:])
return
path.append(A[idx])
findSubset(A, path, idx+1)
path.pop()
findSubset(A, path, idx+1)
findSubset(A,[],0)
for i in res:
x = min(i)
y = max(i)
# calculating the minimum difference
minimum_difference = min(minimum_difference, y-x)
return minimum_difference
# Printing out answer
print(findMinDiff([3, 4, 1, 9, 56, 7, 9, 12],8,5))
C++:
# Python3 program to solve
# chocolate distribution
# problem
def findMinDiff(A,N,M):
res = []
# Initializing our minimum difference
# to minus infinity
minimum_difference = float('inf')
# finding subset
def findSubset(A, path, idx):
if idx == N:
if len(path) == M:
res.append(path[:])
return
path.append(A[idx])
findSubset(A, path, idx+1)
path.pop()
findSubset(A, path, idx+1)
findSubset(A,[],0)
for i in res:
x = min(i)
y = max(i)
# calculating the minimum difference
minimum_difference = min(minimum_difference, y-x)
return minimum_difference
# Printing out answer
print(findMinDiff([3, 4, 1, 9, 56, 7, 9, 12],8,5))
C++:
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// arr[0..n-1] represents sizes of packets
// m is number of students.
// Returns minimum difference between maximum
// and minimum values of distribution.
void findMinDiff(int ind, vector < int > & arr, vector < vector < int >> & ans, vector < int > & ds, int m) {
if (ind == arr.size()) {
if (ds.size() == m) {
ans.push_back(ds);
}
return;
}
// pick up the element
ds.push_back(arr[ind]);
findMinDiff(ind + 1, arr, ans, ds, m);
ds.pop_back();
// Don't pick up the element
findMinDiff(ind + 1, arr, ans, ds, m);
}
public:
vector < vector < int >> MinDiff(vector < int > & candidates, int m) {
vector < vector < int >> ans;
vector < int > ds;
findMinDiff(0, candidates, ans, ds, m);
return ans;
}
};
//main function
int main() {
Solution obj;
// arr to store the chocolates
vector < int > arr {3, 4, 1, 9, 56, 7, 9, 12};
// number of children
int m = 5;
// 2D vector to store the subsets of size m
vector < vector < int >> map = obj.MinDiff(arr, m);
// ans to store minimum difference
int ans = INT_MAX ;
for (int i = 0; i < map.size(); i++) {
int minimum = INT_MAX;
int maximum = INT_MIN;
for (int j = 0; j < map[i].size(); j++){
// Store minimum element of
// the perticular subset
minimum = min(minimum, map[i][j]);
// Store maximum element of
// the perticular subset
maximum = max(maximum, map[i][j]);
}
// Store the difference between
// the maximum and minimum element
int diff = maximum - minimum;
ans = min(ans, diff);
}
cout << "The Minimum difference is " << ans;
cout << endl;
}
Time Complexity : O(2^n) or exponential.
Auxilary Space Complexity : O(2^n) or exponential.
Approach 2: Efficient Solution
The key idea of the efficient approach is that if `m` children are given different numbers of chocolates but the array is sorted, the difference between the maximum and the minimum number of chocolates can be found out with minimum effort. Aiming at this method gives substantially better results in comparison to the brute force technique.
Intuition:
Through the sorting of the array, it's not difficult to know the minimum difference of the subarrays of `m` length in `O(n)` linear time. This is made possible by running through the array in a consecutive manner with a window size of `m` and maintaining track of the maximum and minimum notions of chocolate in each sphere of the window.
Algorithm:
1. Sort the Array:
- First step is to sort the array in ascending order.
2. Initialize Variables:
- Set `answer` variable to integer value `Integer.MAX_VALUE` to hold the minimum difference found so far.
3. Iterate with a Window:
Management can be multidimensional; therefore, it mainly demands the ability to maintain the equilibrium between the financial and social needs of the firm.
- For each iteration, slide the window of size `m` along the array, where `i` starts from `0` to `size - m`, while `size` denotes the length of the array.
4. Calculate Difference:
- For each window, loop times the difference between the max and min values.
- Create two variables: `minimumChocolate == arr[i]` and `maximumChocolate == arr[i+m-1]`.
- Find the difference `maxChocolate - minChocolate` as the result.
5. Update Minimum Difference:
- If the difference after the performed operations is less than the `answer`, you can replace it with a new difference.
6. Return Answer:
- Proceed to go through all windows of the array until the `answer`variable is again given, which is the value indicating the min difference from the packet of the maximum and minimum number of pieces distributed among the students.
Code:
Java:
import java.util.;
public class Main
{
// Function to find the minimum difference
public static int minDifferenceFinder(int[] arr, int size, int m)
{
// If there are no chocolates or
// number of students is 0
if (m == 0 || size == 0)
return 0;
// To store the minimum difference
int answer = Integer.MAX_VALUE;
// Sort the given packets
Arrays.sort(arr);
// Find the subarray of size m
// such that difference between
// last (maximum in case of
// sorted) and first (minimum in
// case of sorted) elements of
// subarray is minimum.
for (int i=0; i<=size-m; i++)
{
int minimumWindow = arr[i];
int maximumWindow = arr[i+m-1];
int gap = maximumWindow- minimumWindow ;
if(gap < answer)
{
answer = gap;
}
}
return answer;
}
//main function
public static void main(String[] args)
{
// arr[0..n-1] represents sizes of packets
int[] arr = {3, 4, 1, 9, 56, 7, 9, 12};
// Number of students
int m = 5;
//Length of arr
int size = arr.length;
//Print minimum difference
System.out.println("Minimum difference is " +minDifferenceFinder(arr, size, m));
}
}
Python:
def findMinDiff(arr, n, m):
# if there are no chocolates or number
# of students is 0
if (m==0 or n==0):
return 0
# Sort the given packets
arr.sort()
# Number of students cannot be more than
# number of packets
if (n < m):
return -1
# Largest number of chocolates
min_diff = arr[n-1] - arr[0]
# Find the subarray of size m such that
# difference between last (maximum in case
# of sorted) and first (minimum in case of
# sorted) elements of subarray is minimum.
for i in range(len(arr) - m + 1):
min_diff = min(min_diff , arr[i + m - 1] - arr[i])
return min_diff
# Driver Code
if __name__ == "__main__":
arr = [3, 4, 1, 9, 56, 7, 9, 12]
m = 5 # Number of students
n = len(arr)
print("The Minimum difference is", findMinDiff(arr, n, m))
C++:
#include <bits/stdc++.h>
using namespace std;
// arr[0..n-1] represents sizes of packets
// m is number of students.
// Returns minimum difference between maximum
// and minimum values of distribution.
int findMinDiff(int arr[], int n, int m)
{
// if there are no chocolates or number
// of students is 0
if (m == 0 || n == 0)
return 0;
// Sort the given packets
sort(arr, arr + n);
// Number of students cannot be more than
// number of packets
if (n < m)
return -1;
// Largest number of chocolates
int min_diff = INT_MAX;
// Find the subarray of size m such that
// difference between last (maximum in case
// of sorted) and first (minimum in case of
// sorted) elements of the subarray are minimum.
for (int i = 0; i + m - 1 < n; i++) {
int diff = arr[i + m - 1] - arr[i];
if (diff < min_diff)
min_diff = diff;
}
return min_diff;
}
int main()
{
int arr[] = { 3, 4, 1, 9, 56, 7, 9, 12 };
int m = 5; // Number of students
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The Minimum difference is "
<< findMinDiff(arr, n, m);
return 0;
}
Time Complexity : O(nlogn)
Space Complexity : O(1)
Conclusion:
In the end, though the Chocolate Distribution Problem keeps it relatively simple, the optimal approach with sorting methods is two times faster than the brute force. By Arranging and Scanning the array over it with a window size of m, we can pick this window that will help in managing the significantly minimum chocolates difference between among the kids in linear, time complexity. This fast and allocative oriented way is not simply speeding up computational operations, but scalability helps to make this method to real-world application with larger data set.
Leave Comment