2.txt

Q Given an array of n integers where each value represents number of chocolates in a packet. Each packet can have variable number of chocolates. There are m students, the task is to distribute chocolate packets such that:
- Each student gets one packet.
- The difference between the number of chocolates in packet with maximum chocolates and packet with minimum chocolates given to the students is minimum.

Complexity- O(nLogn)

#include<iostream>
using namespace std;
 
int main()
{
	int n,k,j,m;
	int dis,min;
	cout<<"\n Enter number of elements in array: ";
	cin>>n;
	int ar[n];
	cout<<"\n Enter the no. of chocoloates in each packet: ";
	for(int i=0;i<n;i++)
	{
		cin>>ar[i];
	}
	
	cout<<"\n Enter Number of students: ";
	cin>>m;
		for(int i=1;i<n;i++)
	{
		k=ar[i];
		j=i-1;
		
		while((ar[j]>k)&&(j>=0))
		{
			ar[j+1]=ar[j];
			j=j-1;
		}
		ar[j+1]=k;
	}
	min=ar[n-1];// in the worst case
    for (int i=0; i+m-1<n; i++) 
    { 
        int dis = ar[i+m-1] - ar[i]; 
        if (dis < min) 
        { 
            min = dis; 
 
        } 
    } 
    cout<<"Minimum difference is: "<<min; 
 
	return 0;
}