Chocolate Distribution Problem

In this article, we will look at the problem of distributing chocolate packets among students in such a way that the difference between the packet with the most chocolates and the packet with the fewest chocolates is minimized.

We have an array of N integers where each element represents the number of chocolates in a packet, and a number m representing the number of students, distribute the packets such that each student receives exactly one packet and the difference between the number of chocolates in the packet with the maximum chocolates and the packet with the minimum chocolates is minimized.

Example

Input: packets = [3, 4, 1, 9, 56, 7, 9, 12], m = 5

Output: 6

Explanation: The packets distributed are [3, 4, 7, 9, 9], and the difference between the maximum (9) and minimum (3) chocolates is 6.

Solution:

To solve this problem, we will use a sorting-based approach. By sorting the array, we can easily find the subarray of size m with the smallest difference between the maximum and minimum elements.

Steps to Solve:

1.    Sort the Array:

o   Sort the array of packets to arrange the chocolates in ascending order.

2.    Find Minimum Difference:

o   Iterate through the sorted array and find the difference between the maximum and minimum chocolates in every possible subarray of size m. Track the minimum difference encountered.

3.    Return Result:

o   Return the minimum difference found.

Time Complexity: NlogN

Space Complexity: O(1)