Chocolate Distribution Problem

Given an array arr[] of n integers where arr[i] represents the number of chocolates in ith packet. Each packet can have a variable number of chocolates. There are m students, the task is to distribute chocolate packets such that: 

• Each student gets exactly one packet.
• The difference between the maximum and minimum number of chocolates in the packets given to the students is minimized.

Examples:

Input: arr[] = {7, 3, 2, 4, 9, 12, 56}, m = 3 
Output: 2 
Explanation: If we distribute chocolate packets {3, 2, 4}, we will get the minimum difference, that is 2.

Input: arr[] = {7, 3, 2, 4, 9, 12, 56}, m = 5 
Output: 7
Explanation: If we distribute chocolate packets {3, 2, 4, 9, 7}, we will get the minimum difference, that is 9 - 2 = 7.

[Naive Approach] By Generating All Subsets

The idea is to generate all subsets of size m of arr[]. For every subset, find the difference between the maximum and minimum elements in it. Finally, return the minimum difference.

[Expected Approach] Using Sliding Window

The idea is to first sort the array, then use sliding window technique to choose consecutive elements to minimize the difference. After sorting the array, the difference between the maximum and minimum values in any window of size m is minimized.

// C++ program to solve chocolate distribution
// problem using Sliding Window

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int findMinDiff(vector<int> &arr, int m) {
	int n = arr.size();
  
    // Sort the given packets
    sort(arr.begin(), arr.end());

    int minDiff = INT_MAX;

    for (int i = 0; i + m - 1 < n; i++) {
      	
      	// calculate difference of current window
        int diff = arr[i + m - 1] - arr[i];
      
      	// if current difference is smaller
      	// then update the minimum difference
        if (diff < minDiff)
        	minDiff = diff;
    }
    return minDiff;
}

int main() {
    vector<int> arr = {7, 3, 2, 4, 9, 12, 56};
    int m = 3;
  	
    cout << findMinDiff(arr, m);
    return 0;
}

// C program to solve chocolate distribution
// problem using Sliding Window

#include <stdio.h>
#include <limits.h>

// Function to compare two elements for qsort
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int findMinDiff(int* arr, int n, int m) {

    // Sort the given packets
    qsort(arr, n, sizeof(int), compare);

    int minDiff = INT_MAX;

    for (int i = 0; i + m - 1 < n; i++) {

        // calculate difference of current window
        int diff = arr[i + m - 1] - arr[i];

        // if current difference is smaller
        // then update the minimum difference
        if (diff < minDiff)
            minDiff = diff;
    }
    return minDiff;
}

int main() {
    int arr[] = {7, 3, 2, 4, 9, 12, 56};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 3;

    printf("%d\n", findMinDiff(arr, n, m));
    return 0;
}

// Java program to solve chocolate distribution
// problem using Sliding Window

import java.util.Arrays;

class GfG {

    static int findMinDiff(int[] arr, int m) {
        int n = arr.length;

        // Sort the given packets
        Arrays.sort(arr);

        int minDiff = Integer.MAX_VALUE;

        for (int i = 0; i + m - 1 < n; i++) {

            // calculate difference of current window
            int diff = arr[i + m - 1] - arr[i];

            // if current difference is smaller
            // then update the minimum difference
            if (diff < minDiff)
                minDiff = diff;
        }
        return minDiff;
    }

    public static void main(String[] args) {
        int[] arr = {7, 3, 2, 4, 9, 12, 56};
        int m = 3;

        System.out.println(findMinDiff(arr, m));
    }
}

# Python program to solve chocolate distribution
# problem using Sliding Window

def findMinDiff(arr, m):
    n = len(arr)

    # Sort the given packets
    arr.sort()

    minDiff = float('inf')

    for i in range(n - m + 1):

        # calculate difference of current window
        diff = arr[i + m - 1] - arr[i]

        # if current difference is smaller
        # then update the minimum difference
        if diff < minDiff:
            minDiff = diff

    return minDiff

if __name__ == "__main__":
    arr = [7, 3, 2, 4, 9, 12, 56]
    m = 3

    print(findMinDiff(arr, m))

// C# program to solve chocolate distribution
// problem using Sliding Window

using System;

class GfG {

    static int findMinDiff(int[] arr, int m) {
        int n = arr.Length;

        // Sort the given packets
        Array.Sort(arr);

        int minDiff = int.MaxValue;

        for (int i = 0; i + m - 1 < n; i++) {

            // calculate difference of current window
            int diff = arr[i + m - 1] - arr[i];

            // if current difference is smaller
            // then update the minimum difference
            if (diff < minDiff)
                minDiff = diff;
        }
        return minDiff;
    }

    static void Main() {
        int[] arr = {7, 3, 2, 4, 9, 12, 56};
        int m = 3;

        Console.WriteLine(findMinDiff(arr, m));
    }
}

// JavaScript program to solve chocolate distribution
// problem using Sliding Window

function findMinDiff(arr, m) {
    let n = arr.length;

    // Sort the given packets
    arr.sort((a, b) => a - b);

    let minDiff = Number.MAX_SAFE_INTEGER;

    for (let i = 0; i + m - 1 < n; i++) {

        // calculate difference of current window
        let diff = arr[i + m - 1] - arr[i];

        // if current difference is smaller
        // then update the minimum difference
        if (diff < minDiff)
            minDiff = diff;
    }
    return minDiff;
}

let arr = [7, 3, 2, 4, 9, 12, 56];
let m = 3;

console.log(findMinDiff(arr, m));

2

Time Complexity: n*log(n), where n is the size of arr[].
Auxiliary Space: O(1)