Chocolate Distribution Problem || Program 15 || Competitive Coding || Learning Monkey ||

Chocolate Distribution Problem
In this class, We discuss Chocolate Distribution Problem.
The reader can take a full competitive coding course. 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 lt 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)
Link for playlists:
https://www.youtube.com/channel/UCl8x4Pn9Mnh_C1fue-Yndig/playlists


Link for our website: https://learningmonkey.in

Follow us on Facebook @ https://www.facebook.com/learningmonkey

Follow us on Instagram @ https://www.instagram.com/learningmonkey1/

Follow us on Twitter @ https://twitter.com/_learningmonkey

Mail us @ [email protected]