Chocolate Distribution Problem Easy 0 attempts
GeeksforGeeks ↗

Chocolate Distribution Problem

Easy ArrayTwo Pointers GeeksforGeeks

Given an array A[] of positive integers of size N, where each value represents the number of chocolates in a packet. There are M students, the task is to distribute chocolate packets 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.

Sample Input
N = 8, M = 5, A = [3, 4, 1, 9, 56, 7, 9, 12]
Sample Output
6
Constraints
  • 1 <= N <= 10^5
  • 1 <= A[i] <= 10^9
  • 1 <= M <= N
Test Cases
Case 1
Args: [[3,4,1,9,56,7,9,12],8,5] Expected: 6
Topics
ArrayTwo Pointers

Sort the array. Then slide a window of size m across the sorted array and find the window where the difference between the last and first element is minimized.

function findMinDiff(arr, m) {
  if (m === 0 || arr.length === 0) return 0;
  arr.sort((a, b) => a - b);

  let minDiff = Infinity;
  for (let i = 0; i + m - 1 < arr.length; i++) {
    const diff = arr[i + m - 1] - arr[i];
    minDiff = Math.min(minDiff, diff);
  }

  return minDiff;
}

Time: O(n log n) for sorting Space: O(1) (ignoring sort space)

Saved in this browser only. Private to you.

JavaScript