Chocolate Distribution Problem

In this class, We discuss Chocolate Distribution Problem.

The reader can take a full competitive coding course. Click Here.

For Complete YouTube Video: Click Here

Question:

Given N chocolate packets.

Each packet contains x number of chocolates. x value given in a list.

Example:

N = 8

Each packet contains x number of chocolates [ 3, 4, 1, 9, 56, 7, 9, 12]

The m value is given.

M = 5, i.e. five kids are present.

Each kid is given one chocolate packet in such a way that the difference between the packet with maximum chocolates and the packet with minimum chocolates is minimum.

Output:

The kids are assigned with [3, 4, 9, 7, 9]

9-3 = 6

The difference is 6.

The program should output 6

The above distribution will give the minimum difference = 6

Time complexity = O(nlogn)

Space complexity = O(1)

Solution:

One way:

Pick all the combinations of five packets from the given list.

But picking all the five combinations needs time complexity of O(n^5)

Second way:

Are all the five number combinations required in our example? No.

We can eliminate a few five-number combinations.

Which combinations can be eliminated?

Arrange the elements in ascending order. And pick the element’s five numbers set in sequence and find the difference.

A detailed explanation is provided in the video.

Code:

class Solution:

    def findMinDiff(self, arr,n,m):

        if (m == 0 or n == 0):

            return 0

        arr.sort()

        if (n < m):

            return -1

        min_diff = arr[n-1] – arr[0]

        for i in range(len(arr) – m + 1):

            min_diff = min(min_diff,  arr[i + m – 1] – arr[i])

        return min_diff

print(“enter n value”)

n = int(input())

print(“enter m value”)

m = int(input())

print(“enter n values”)

arr=list(map(int,input().strip().split()))

ob = Solution()

k = ob.findMinDiff(arr,n,m)

print(k)