Chocolate Distribution Problem

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

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.

Example 1:

Input:
N = 8, M = 5
A = {3, 4, 1, 9, 56, 7, 9, 12}
Output: 6
Explanation: The minimum difference between 
maximum chocolates and minimum chocolates 
is 9 - 3 = 6 by choosing following M packets :
{3, 4, 9, 7, 9}.

Example 2:

Input:
N = 7, M = 3
A = {7, 3, 2, 4, 9, 12, 56}
Output: 2
Explanation: The minimum difference between
maximum chocolates and minimum chocolates
is 4 - 2 = 2 by choosing following M packets :
{3, 2, 4}.

Your Task:

You don't need to take any input or print anything. Your task is to complete the function findMinDiff() which takes array A[ ], N and M as input parameters and returns the minimum possible difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student.

Expected Time Complexity: O(N*Log(N))

Expected Auxiliary Space: O(1)

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 105

1 ≤ Ai ≤ 109

1 ≤ M ≤ N

Solution:

To sort the array so that the number of chocolates are in increasing order, we can now be sure that the adjacent elements are the pair with the least difference.

Now for each packet check, let say i, could we distribute this packet to the children till the (i + m - 1)th packet? Also keep track of the minimum difference.

Post the complete iteration of the array you got your result.

class Solution {
    public long findMinDiff (ArrayList<Integer> a, int n, int m) {
        // your code here
        if (m > n) {
            // throw new IllegalArgumentException("Number of students less than packets");
            return -1;
        }
        int min = Integer.MAX_VALUE;
        Collections.sort(a);
        for (int i = 0; i + m - 1 < a.size(); i++) {
            min = Math.min(min, a.get(i + m - 1) - a.get(i));
        }
        return min;
    }
}