Chocolate Distribution Problem

ARRAYS

Problem statement:

Given an array A[ ] of positive integers of size N, 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 among M students such that :
1. Each student gets exactly one packet.
2. The difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student is minimum.

https://practice.geeksforgeeks.org/problems/chocolate-distribution-problem3825/1

Here, they have given the size of array, array elements and the number of students as inputs which are as follows:

1.n = size of array

2.a[] = array

3.m = no. of students

The array elements represents the number chocolates in a packet.

WE NEED TO FIND :

Minimum difference between maximum and minimum elements in the subarray of size m.

Steps to arrive at the solution:

1. Sorting:

Instead of finding all the possible subarrays, we are first sorting the given array using in-bulit sort function.(in order to optimize the code )

sort(arr,arr+n);

2.Assigning the last value:

Then we are going to declare a variable, say, “mini” and we are assigning the value of last array index to it which will be the largest value in that array as we have sorted the array priorly.

mini = arr[n-1] (n is the size of the array)

3.Loop until we find the answer:

Now, we are going to find the actual answer which is minimum difference between the maximum and minimum value of the subarray.

for(int i=0;i<n-m+1;i++)

In the above line, n represents size of array and m represents size of subarray(number of students).

And by this expression, “i<n-m+1” we mean that from the given index till the size of the subarray in the given array. And +1 is added since array indices start from 0.

For instance , say n = 8 and m= 5 and n-m-1=4 :

From the above diagram, you can see that from the given index, it loops until the next 5 elements which is nothing but the size of subarray.And as i becomes 1, then it’ll loop until 5th index and so on.

Now, here we can’t take i≤m since the index value of first element keeps changing.

dif = arr[i+m-1]-arr[i]

Here, we are finding the difference between the first element and the last element of the highlighted subarray. arr[i+m-1] represents the last index of the highlighted subarray, which is 4 in our case and arr[i] is nothing but the first value whose index value is 0.

if(dif<mini)
{
mini = dif;
}

And by using the above if statement, we get the least difference between the first and last element of the subarray in the loop.

And the final step is nothing but to return the given answer.

Time complexity: O(nlogn)