2. Chocolate Distribution Problem.md

We are given an array of N positive integers. Each of the numbers represents a packet of chocolate, where the number is the number of chocolates in the packet. There are M students in a classroom, and we have to distribute these packets to those students such that: Every student must get a packet of chocolate. The difference between the maximum chocolate packet and the minimum chocolate packet should be minimum. We have to find that difference.

Example 1:
Input: [5 7 2 8 4 3], M = 3
Output: 2
Explanation: 6 packets are to be distributed in 3 students. If we give packets with 2, 3, and 4 chocolates to these 3 students, then the difference will be minimum, 4 - 2 = 2.
Example 2:
Input: [2 14 11 12 17], M = 4
Output: 6
Explanation: Packets with 11, 12, 14 and 17 chocolates are distributed to 4 students and the minimum difference is 17 - 11 = 6

Algorithm

• Sort the array.
• When We sort the array we can take a window of "m" elements and can check minimum difference in every window of size m.

int chocolate_distribution(vector<int> &input, int m){

	// variable to hold the size of the input array
	int n = input.size();

	// sort the array
	sort(input.begin(), input.end());

	// variable to hold the minimum difference
	int min_diff = 1000000; // assigned a very big value

	// process every window of size m of the sorted array
	for( int i = 0; i < n-m; i++){
		// difference between maximum and minimum
		int diff = input[i+m-1] - input[i];
		
		// if current difference is minimum then update the min_diff
		min_diff = min(min_diff, diff);
	}

	// return the result
	return min_diff;
}