6. Chocolate Distribution Problem

Topic :

arrays

Difficulty :

easy

Problem Link :

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.

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

ALGORITHM

A simple solution is to generate all subsets of size m of arr[0..n-1]. For every subset, find the difference between the maximum and minimum elements in it. Finally, return the minimum difference. An efficient solution is based on the observation that to minimize the difference, we must choose consecutive elements from a sorted packet. We first sort the array arr[0..n-1], then find the subarray of size m with the minimum difference between the last and first elements.

import java.io.*;
import java.util.*;
 class Chocolate_Distribution
{
 public static void main (String args[])
 { 
     int arr[]={3, 4, 1, 9, 56, 7, 9, 12};
     int n=arr.length;
     int m=5;
     System.out.println(findMinDiff(arr,n,m));
    }
    
 public   static int findMinDiff(int arr[], int n, int m)
 {
     if(n==0||m==0)
     return 0;
     if(n<m)
     return -1;
     Arrays.sort(arr);
     int minDiff=Integer.MAX_VALUE;
     
     for(int i=0;i+m-1<n;i++)
     { int curr_minCandy=arr[i];
         int curr_maxCandy=arr[i+m-1];
         
         minDiff=Math.min(minDiff,curr_maxCandy-curr_minCandy);
         
        }
     return minDiff;
    }
}