Let's start by understanding the problem statement of the Chocolate Distribution problem.
You are given an array that contains the number of chocolates in a packet and the total number of students your work is to distribute the chocolates in such a way that the difference between the packet with the highest number of chocolates and the packet with the lowest number of chocolates is minimum.
Hint:
For designing an algorithm for such a problem statement we need to take the integers from the array in a range of m, since the number of packets cannot be less than the number of students, and select the main difference in the range and print the result.
Quick Think:
Before proceeding we need to have a look at the conditions required for this problem statement which are mentioned below:-
-
One of the conditions should be that the number of chocolates in a packet should not be less than the number of students.
-
The second condition should be that the number of chocolates in a packet should be selected from a sorted array (using merge sort) of the number of chocolates to get the difference between the packet with the most number of chocolates and the packet with the least number of chocolates.
-
And the other condition should be that if the number of chocolates in the packet or the number of students is 0 then the algorithm should return 0 and terminate.
Algorithm:
Declare a function to find the minimum difference between the number of chocolates in a packet with arguments as the array, the size of the array, and the total number of students and follow the steps below to reach the solution:-
Step1: Check for the condition that the number of chocolates in a packet or the total number of students is not 0 if yes, then return 0 and terminate else go to step 2.
Step2: Sort the array (here we will use merge sort for best time complexity) and define a variable to be the maximum integer in the range using INT_MAX STL in C++.
Step3: Define two variables say, left and right, the left will represent the index from the left side of the array, and the right will represent the index on the right side of the array and select the range in the array for the students, initially define them to be 0.
Step4: Now, keep traversing the array and check for the difference between the highest packet containing chocolates and the packet containing the least number of chocolates in the range of m students, and if the difference comes out to be less than the variable defined in step 2 then store the minimum result and repeat the step 4, and store the index to the left and the right variable to return or print the final result.
Implementation of the Above Algorithm:
Now let's see the implementation of the above algorithm,
#include <bits/stdc++.h>
using namespace std;
/*Function to sort the given array (Merge Sort). */
void sort(int arr[], int low, int mid, int high)
{
int i, j, k;
int n1 = mid - low + 1;
int n2 = high - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[i + low];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = low;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
k++;
i++;
}
while (j < n2)
{
arr[k] = R[j];
k++;
j++;
}
}
/*Function to sort the given array (Merge Sort). */
void merge(int arr[], int low, int high)
{
if (low < high)
{
int mid = low + (high - low) / 2;
merge(arr, low, mid);
merge(arr, mid + 1, high);
sort(arr, low, mid, high);
}
}
/*Function to find the min difference. */
int findmin(int arr[], int n, int m, int low)
{
/*if there are no chocolates or number
of students is 0. */
if (m == 0 || n == 0)
return 0;
/*Sort the given packets. */
merge(arr, low, n - 1);
/*Number of students cannot be more than
number of packets.*/
if (n < m)
return -1;
/*Largest number of chocolates. */
int update_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 subarray is minimum. */
int left = 0, right = 0;
for (int i = 0; i + m - 1 < n; i++)
{
int diff = arr[i + m - 1] - arr[i];
if (diff < update_diff)
{
update_diff = diff;
left = i;
right = i + m - 1;
}
}
return (arr[right] - arr[left]);
}
/*Driver function to check the above algorithm. */
int main()
{
int arr[] = { 7, 3, 2, 4, 9, 12, 56 };
int m = 3; // Number of students
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum difference is " <<
findmin(arr, n, m, 0);
return 0;
}
The time complexity of the above algorithm is:- O(nlogn).
The output of the above algorithm is:- Minimum difference is 2.
Explanation of the above Algorithm:
Let us consider an array consisting of the number of chocolates with the number of students 3 as shown in the diagram above. Follow the steps below to understand the above algorithm:-
- Since the number of packets is not less than the number of students, so, we continue with our algorithm.
- Next, we will sort our array using merge sort, as shown in the diagram above.
- Next, we will define the left and the right index as 0, as shown in the above diagram.
- Now, we will traverse the array and check for the difference between the left index and the element at the index m - 1, to take the packet of chocolates in the required range of a number of students the difference.
- Now, since the diff is less than the value of update diff which stores INT_MAX will now store the value of diff as shown in the above diagram.
- And, now we move on to the next packet and hence, now the diff is as shown in the diagram above.
- Since now our updated difference is 2 and the current difference is 4 so since, the current difference is not less than the updated difference so, there is no change in the min difference, and we move on to the next packet in the array as shown in the diagram above.
- Similarly, the difference now is 5 and our updated difference is 2 the current difference is not less than the updated difference so, there is no change in the min difference, and we move on to the next packet in the array as shown in the above diagram.
- Again, the difference now is 5 and our updated difference is 2 the current difference is not less than the updated difference so, there is no change in the min difference, and we move on to the next packet in the array as shown in the above diagram.
- And, repeating the above steps we get the final result as the minimum difference of the element at index 2 and 0 i.e., 2.
