Chocolate Distribution Problem
Problem
arr[i] is the number of chocolates in packet i. Give one packet to each of m students so that the difference between the largest and smallest packet handed out is as small as possible. Return that minimum difference.
Example 1
Input: arr = [7, 3, 2, 4, 9, 12, 56], m = 3 Output: 2
Choose packets 2, 3 and 4: 4 − 2 = 2.
Also asked as: Chocolate Distribution problem
Test cases
Case 1
Input: [7,3,2,4,9,12,56], 3 Expected: 2
Case 2
Input: [3,4,1,9,56,7,9,12], 5 Expected: 6
Case 3
Input: [1,2,3], 3 Expected: 2
Case 4
Input: [5], 1 Expected: 0
View solutionHide solution1 approach
1. Sort + sliding window of size m
Time O(n log n)Space O(1)
After sorting, the fairest set of m packets is a contiguous window; minimise (window max − window min).
function minDiff(a, m) { a.sort((x, y) => x - y); let best = Infinity; for (let i = 0; i + m - 1 < a.length; i++) { best = Math.min(best, a[i + m - 1] - a[i]); } return best;}