Chocolate Problem
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.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.
The first line of each test case contains two space-separated integers ‘N’ denoting the number of packets of chocolate and ‘M’ denotes the number of students.
The second line of each test case contains ‘N’ space-separated integers denoting the number of chocolate in each of ‘N’ packets.
Output Format :
For each test case, print the minimum difference of the chocolates contained in the packets distributed to the students.
Note :
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
2 <= M <= N <= 10^4
1 <= CHOCOLATES[i] <= 10^9
Time Limit : 1 sec
CodingNinjas
author
2y
Recursion
The idea is that generate all the possible subsets of size ‘M’ and checks the minimum difference that can be possible from all subsets.
- This problem can be solved using recursion and the ide...read more
CodingNinjas
author
2y
Sliding Window
The idea is based on the observation that to minimize the difference between a maximum number of chocolate in a packet and a minimum number of chocolate in the packet is that, always cho...read more
Chowdam Mounika
2y
Foe each case print the minimum difference of the chocolates contained in the packets distributed in the student
Anonymous
2y
For each case print the minimum difference of the chocolates contained in the packets distributed to the student.
Add answer anonymously...
Top Wipro Data Analyst interview questions & answers
Popular interview questions of Data Analyst
Top HR questions asked in Wipro Data Analyst
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app