## Problem Statement

In the above chocolate distribution problem, you will be given an array of n integers where each value represents the number of chocolates in a packet. Each packet can have a variable number of chocolates. There are m students, the task is to distribute chocolate packets such that:

**Rules :**

- Each student gets only one packet.
- The difference between the number of chocolates in the packet with
**maximum**chocolates and the packet with**minimum**chocolates given to the students is**minimum**. - However, it is not necessary that all packets should be distributed among the children.

**Input Format :**

- Array Length n
- Array’s element of size n
- number of children m

**Output Format :**

- Return an integer containing the minimum difference between the number of chocolates in the packet with
**maximum**chocolates and the packet with**minimum**chocolates.

## Example

**Input :** arr[] = {3, 4, 1, 9, 56, 7, 9, 12}

m = 5

**Output :**

```
Minimum Difference is 6.
```

## Explanation

Let us now understand the above example of chocolate distribution problem in detail.

- In the above example, there are eight packets and five children. The number of chocolates in each packet is 3 4 1 9 56 7 9 12 respectively.
- Let us say that the packet which contains 1, 3, 4, 7, and 9 is been distributed among the 5 children, so the difference between the number of chocolates in the packet with
**maximum**chocolates and the packet with**minimum**chocolates would be**9 – 1 = 8**. - Let us say that the packet which contains 3, 4, 7, 9, and 9 is been distributed among the 5 children, so the difference between the number of chocolates in the packet with
**maximum**chocolates and packet with**minimum**chocolates would be**9 – 3 = 6**. - Let us say that the packet which contains 4, 7, 9, 9, and 12 is been distributed among the 5 children, so the difference between the number of chocolates in the packet with
**maximum**chocolates and packet with**minimum**chocolates would be**12 – 4 = 8**. - Let us say that the packet which contains 7, 9, 9, 12, and 56 is been distributed among the 5 children, so the difference between the number of chocolates in the packet with
**maximum**chocolates and packet with**minimum**chocolates would be**56 – 7 = 49**.

and so on.

So above all the assumptions we can see the minimum difference between maximum chocolates and minimum chocolates is **9 – 3 = 6** by choosing the following M packets : **{3, 4, 9, 7, 9}**.

## Constraints

1 ≤ N ≤ 10^5

1 ≤ Ai ≤ 10^9

1 ≤ M ≤ N

## Approach 1: Brute Force

Let us begin with the **brute force** approach of chocolate distribution problem, which is too slow but should be mentioned during the interview.

**Intution :** In this approach, at first, we will find all the subsets of length m (children) from the given array and then we will choose the one with the minimum difference between the lowest and the maximum value.

**Algorithm :**

Here is the brute force algorithm for this particular problem:

- Firstly, we are going to take a double dimension (2D) ArrayList data structure to store all the subsets of length m in it.
- Then we will follow a recursive approach to find all the subsets of size m from the given array.
- We will have a recursive function which will contains the
**array**,**index**of elements inside the array starting with**0**index,**double dimension**(2D)**ArrayList**,**single dimension**(1D)**ArrayList**to store the current subset, and**m**(size of subset), as**arguments**. - Inside the recursive function there will be a
**base case**and**recursive steps**. Let us discuss them.

**Recursive Steps :**

*//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 :**

Basically, a **subset** of an array can be formed by choosing some (maybe 0, 1, 2, … or equal to the size of the array) elements out of all the possible array elements, in the same order in which they appear in the original array. So every element in the array has its chance of including itself or excluding itself from the subset. In the above recursive steps, we have two recursive calls, one after including the element in the subset (adding the element in the 1D ArrayList) and another after excluding the element from the subset.

**Note :** We are removing the last visited element from the ArrayList, because the ArrayList stores the element by reference and it will not remove the element automatically while returning, so we have to remove it manually.

But when this including and excluding of elements from the array will continue, and when will be the actual ending of this process. for that we need a **base case**

**Base Case :**

```
if(index == array's length){
if(1D ArrayList size == m){
Store the subset of 1D ArrayList inside the
2D ArrayList.
}
return;
}
```

**Explanation :**

In the above base case we can see, that when the index surpasses the length of the array, we are stopping the process. At that time we also check whether the size of the 1D ArrayList is equal to m, if it is the case, then we know we have got the subset of size m from the array. So we will store it in our 2D ArrayList and return it.

- We will use an answer variable to store the minimum difference between the lowest and the maximum value of every subset.
- Initialize the answer variable with Integer.MAX_VALUE.
- After getting all the subsets of size m of the given array in our 2D ArrayList, we will now iterate throughout the 2D ArrayList.
- While iterating we will keep storing the minimum difference between the lowest and the maximum value of every subset (1D ArrayList) from the 2D ArrayList in our answer variable.
- we print the answer.

### Code

Now, let us see the code of chocolate distribution problem in different programming languages.

**Code in JAVA :**

*// JAVA Code For Chocolate Distribution*
*// Problem*
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);
}
}

**Output :**

```
6
```

**Code in Python :**

*# 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))

**Output :**

```
6
```

**Code in C++**

*// C++ program to solve chocolate distribution*
*// problem*
#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;
}

**Output :**

```
The Minimum difference is 6
```

### Complexity Analysis

This is a brute-force approach to the chocolate distribution problem, and it will have a very inefficient solution, with very high time and space complexity.

### Time Complexity :

As there are two recursive calls inside the recursive function, it will take exponential **O(2^n)** time, also we are performing the iteration throughout the 2d ArrayList which will again take **O(2^n)** time as the total elements will be nearly equal to **2^n** (all subsets) where n is the total element of the array.

**Time Complexity : O(2^n) or exponential.**

### Space Complexity :

As we are taking a 2D ArrayList to store all the subsets of the array. So it will take **O(2^n)** space as the total subset of any array is **2^n**. The recursive call will also take some space in the stack memory.

**Auxilary Space Complexity : O(2^n) or exponential.**

## Approach 2: Efficient solution

Now let us look at the efficient solution of chocolate distribution problem, which will be much more optimal than brute force.

**Intuition :**

In the problem statement of chocolate distribution problem, they are asking us to get the minimum difference between the maximum and minimum chocolate given to m children. If we see the problem statement properly, we can observe that if the array is **sorted**, then the minimum difference of subarrays of size m can be easily found in O(n) time.

For example, Let’s assume for the given array above, the number of students is 3 (m = 3). After sorting the array, just one iteration with a window of size 3 will give us the minimum difference. Here’s how:

**At first sort the array :**

Hence, the minimum difference of subarrays of size m can be easily found in O(n) time.

**Algorithm :**

Here is the optimal algorithm for this particular problem:

- Firstly, we will sort the array so that it is easy to calculate the difference between the maximum and minimum chocolates.
- Then we will initialize an
**answer**variable with Integer.MAX_VALUE (because we are supposed to find the minimum), where we will store the minimum difference. - Then we will iterate with a window of size m, that is, from i = 0 to i = size – m (where m is the number of children).
- Then we will initialize a
**minimumChocolate**variable to arr[i] and**maximumChocolate**variable to arr[i+m-1]. - Then we will initialize a
**difference**variable which will contain the difference between the**maximumChocolate**and the**minimumChocolate**variable maximumChocolate – minimumChocolate. - Then we will check if the
**difference**variable is less than the**answer**variable. - If it is true we will update our
**answer**variable to the**difference**variable. - After iteration is completed, we will just return the
**answer**and that will be our required answer.

### Code

Now, let us see the code of chocolate distribution problem in different programming languages.

**Code in JAVA :**

*// JAVA Code For Chocolate Distribution*
*// Problem*
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));
}
}

**Output :**

```
6
```

**Code in Python :**

*# Python3 program to solve*
*# chocolate distribution*
*# problem*
*# arr[0..n-1] represents sizes of packets*
*# m is number of students.*
*# Returns minimum difference between maximum*
*# and minimum values of the distribution.*
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))

**Output :**

```
The minimum difference is 6
```

**Code in C++ :**

*// C++ program to solve chocolate distribution*
*// problem*
#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;
}

**Output :**

```
The minimum difference is 6
```

### Complexity Analysis

This is the most optimal approach, and it will have a very efficient solution, with very less time and space complexity.

### Time Complexity

As we are sorting the array at first, which will take **O(nlogn)** time which will overshadow the linear iteration of the sorted array which will take **O(n)** time. Hence, the time complexity is **O(nlogn)**.

**Time Complexity : O(nlogn).**

### Space Complexity

Assuming we are using an **in-place** sorting algorithm, Hence, the space complexity will be constant **O(1)**.

**Space Complexity : O(1).**

## Conclusion

In this article, we learned about the problem, the chocolate distribution problem. Let us recap the points we discussed throughout the article:

- Basically, in the chocolate distribution problem, we will be given an array and number of children, and we have to find the difference between the number of chocolates in the packet with
**maximum**chocolates and the packet with**minimum**chocolates given to the students is**minimum**. - Firstly, we applied the
**brute force**approach in which we will find all the subsets of size m (number of children) from the array, and iterate over them, and find the minimum difference. - In the
**brute force**approach, the time complexity will be exponential**O(2^n)**, and also the space complexity will be exponential**O(2^n)**. This approach is very inefficient and slow. - Then, we applied the
**optimal**approach, in which we will use the**sorting**technique. - At first, we will sort the given array, then we will iterate over the array with a window of size m (number of children) and keep storing the minimum difference.
- In the
**optimal**approach, the time complexity will be only**O(nlogn)**and the space complexity will be**O(1)**. This approach is very efficient and fast.

## Frequently Asked Questions

**How should we approach a problem like this?****Answer :**Firstly, you need to understand the problem properly. Then think of a algorithm for this problem. Then begin with the Brute Force approach. Later, try to optimise your code.- What is the minimisation problem?
**Answer :**Finding the minimum possible value for the given function. - Which is the best sorting algorithm?
**Answer :**Merge Sort algorithm is the best sorting algorithm.