Discussion on Chocolate Distribution Problem

Posted by Akshay Sharma on June 17th, 2022

In this article, we will tackle the famous Chocolate Distribution Problem and discuss it in detail. Hence we are going to discuss the solution to the chocolate distribution problem and cover all the other aspects of the problem.

Question statement:

We are given N packets of chocolates; the task is to distribute those packets among M children. Each one gets a single packet, and the difference between a packet containing maximum chocolates and a packet containing minimum chocolates should be minimized.

Example 1

If there are six packets and three children. The number of chocolates in each packet is 5 7 2 8 4 3, respectively.

Say that the packets containing 2, 5 and 7 chocolates are distributed among three children, so the difference would be 7-2=5.

Say that the packets containing 3, 4 and 8 chocolates are distributed among three children, so the difference would be 8-4 =4.

Say that the packet containing 2, 3 and 4 chocolates are distributed among three children, so the difference would be 4-2 =2.

And so on.

Let us take another example to understand the question a bit more clearly.

Example 2 

If there are five packets and four children. The number of chocolates in each packet is 2 14 11 12 17, respectively.

Say that the packets containing 2, 11, 12, and 14 chocolates are distributed among four children, so the difference would be 14-2=12.

Say that the packets containing 2, 11, 12, and 17 chocolates are distributed among four children, so the difference would be 17-2 =15.

Say that the packet containing 11, 12, 14, and 17 chocolates are distributed among three children, so the difference would be 17-11 =6.

And so on.

Referring to the above examples we have to find the minimum difference between the packets containing the highest and lowest number of chocolates.

Approach

Brute-force Approach

In the brute-force approach, we take all the subsets of the array and find the minimum difference between the packets containing the highest and lowest number of chocolates.

This approach can be mentioned in an interview, however, it is redundant in any coding contest because of its exponential time complexity.

Sorting

Sorting is an efficient approach to this problem.

Algorithm

• Sort the given array.

• Start traversing the array from the starting index till the starting point of the last window.

• Calculate the difference between the maximum and the minimum window at each iteration.

• Store the minimum value among all the calculated values in the previous step. This will be our required answer.

Time Complexity: O(nLogn)

Where n is the length of the array

Space Complexity: O(1)

C++ Implementation 

#include<bits/stdc++.h>

#include

using namespace std;

int main()

{

    //declaring number of testcases

    int t;

    cin>>t;

    //For each testcase

    while(t-->0){

        //declaring number of elements in an array

        int n;

        cin>>n;

        //declaring elements in array

        int a[n];

        for(int i=0; i<n; i++){

            cin>>a[i];

        }

        //declaring number of students

        int m;

        cin>>m;

        //sorting the array

        sort(a, a+n);

        int min=INT_MAX;

        //Since there are n packets, and m children

        //Number of maximum set possible will be n-m.

        for(int i=0; i<n-m; i++){

            //Finding max.

            int maxWindow=a[i+m-1];

            //Finding min.

            int minWindow=a[i];

            //Noting the gap.

            int gap=maxWindow-minWindow;

            //Checking which gap results in minimum.

            if(gap<min){

                min=gap;

            }

        }

        //Displaying result.

        cout<<min<<endl;

    }

    return 0;

}

Sample Input: 

12, 4, 7, 9, 2, 23, 25

4

Sample Output: 

7