# Chocolate Problem

Moderate
0/80
Average time to solve is 15m
Contributed by

## Problem statement

Given an array/list of integer numbers 'CHOCOLATES' of size 'N', where each value of the array/list represents the number of chocolates in the packet. There are â€˜Mâ€™ number of students and the task is to distribute the chocolate to their students. Distribute chocolate in such a way that:

1. Each student gets at least one packet of chocolate.

2. The difference between the maximum number of chocolate in a packet and the minimum number of chocolate in a packet given to the students is minimum.

Example :

``````Given 'N' : 5 (number of packets) and 'M' : 3 (number of students)
``````

``````And chocolates in each packet is : {8, 11, 7, 15, 2}

All possible way to distribute 5 packets of chocolates among 3 students are -

( 8,15, 7 ) difference of maximum-minimum is â€˜15 - 7â€™ = â€˜8â€™
( 8, 15, 2 ) difference of maximum-minimum is â€˜15 - 2â€™ = â€˜13â€™
( 8, 15, 11 ) difference of maximum-minimum is â€˜15 - 8â€™ = â€˜7â€™
( 8, 7, 2 ) difference of maximum-minimum is â€˜8 - 2â€™ = â€˜6â€™
( 8, 7, 11 ) difference of maximum-minimum is â€˜11 - 7â€™ = â€˜4â€™
( 8, 2, 11 ) difference of maximum-minimum is â€˜11 - 2â€™ = â€˜9â€™
( 15, 7, 2 ) difference of maximum-minimum is â€˜15 - 2â€™ = 13â€™
( 15, 7, 11 ) difference of maximum-minimum is â€˜15 - 7â€™ = â€˜8â€™
( 15, 2, 11 ) difference of maximum-minimum is â€˜15 - 2â€™ = â€˜13â€™
( 7, 2, 11 ) difference of maximum-minimum is â€˜11 - 2â€™ = â€˜9â€™

Hence there are 10 possible ways to distribute â€˜5â€™ packets of chocolate among the â€˜3â€™ students and difference of combination (8, 7, 11) is â€˜maximum - minimumâ€™ = â€˜11 - 7â€™ = â€˜4â€™ is minimum in all of the above.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 50
2 <= M <= N <= 10^4
1 <= CHOCOLATES[i] <= 10^9

Time Limit : 1 sec
``````
##### Sample Input 1 :
``````2
3 2
7 2 4
4 3
3 5 1 6
``````
##### Sample Output 1 :
``````2
3
``````
##### Explanation For Sample Input 1 :
``````Test Case 1 :

All possible way to distribute 3 packets of chocolate among 2 students are -

( 7, 2 ) difference is â€˜7 - 2â€™ = â€˜5â€™
( 7, 4 ) difference is â€˜7 - 4â€™ = â€˜3â€™
( 2, 4 ) difference is â€˜4 - 2â€™ = â€˜2â€™

There are three ways to distribute 3 packets of chocolate among 2 students but pair ( 4, 2 ) has minimum difference in â€˜maximum - minimumâ€™ = â€˜4 - 2â€™ = â€˜2â€™

Test Case 2 :

All possible way to distribute 4 packets of chocolate among 3 students are -

( 3, 5, 1 )  difference is â€˜5 - 1â€™ = â€˜4â€™
( 5, 1, 6 )  difference is â€˜6 - 1â€™ = â€˜5â€™
( 1, 6, 3 )  difference is â€˜6 - 1â€™ = â€˜5â€™
( 6, 5, 3 )  difference is  â€˜6 - 3â€™ = â€˜3â€™

There are four options to choose 3 packets of chocolate. Only ( 6, 5, 3 ) pair has the minimum difference â€˜6 - 3â€™ = â€˜3â€™ comparing other pair of difference ( 4, 5, 5 )
``````2
``````2