forked from imsushant12/GFG-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Chocolate_Distribution_Problem.cpp
49 lines (43 loc) · 1.8 KB
/
Chocolate_Distribution_Problem.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
Problem Statement:
------------------
Given an array A[ ] of positive integers of size N, where each value represents the number of chocolates in a packet. Each packet can have a variable number of chocolates.
There are M students, the task is to distribute chocolate packets among M students such that :
1. Each student gets exactly one packet.
2. The difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student is minimum.
Example 1:
---------
Input:
N = 8, M = 5
A = {3, 4, 1, 9, 56, 7, 9, 12}
Output: 6
Explanation: The minimum difference between maximum chocolates and minimum chocolates is 9 - 3 = 6 by choosing following M packets : {3, 4, 9, 7, 9}.
Example 2:
---------
Input:
N = 7, M = 3
A = {7, 3, 2, 4, 9, 12, 56}
Output: 2
Explanation: The minimum difference between maximum chocolates and minimum chocolates is 4 - 2 = 2 by choosing following M packets : {3, 2, 4}.
Your Task: You don't need to take any input or print anything. Your task is to complete the function findMinDiff() which takes array A[ ], N and M as input parameters
and returns the minimum possible difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student.
Expected Time Complexity: O(N*Log(N))
Expected Auxiliary Space: O(1)
*/
// Link --> https://practice.geeksforgeeks.org/problems/chocolate-distribution-problem3825/1
// Code:
class Solution
{
public:
long long findMinDiff(vector<long long> a, long long n, long long m)
{
sort(a.begin(), a.end());
long long minDifference = INT_MAX;
for(long long i=0 ; i<(n-m+1) ; i++)
{
if(abs(a[i] - a[i+m-1]) < minDifference)
minDifference = abs(a[i] - a[i+m-1]);
}
return minDifference;
}
};