Arrays: Chocolate Distribution Problem

The chocolate distribution problem states that we are given an array in which each element represents the number of chocolates in that packet. We are also given the number of students

We have to distribute the chocolate packet to students with the given conditions:

1. Make sure that each student gets only one packet.
2. The difference between the packet with maximum chocolates and the packet with minimum chocolates in minimum.

For example:

We have given an array and there are 5 students. If we distribute packets [ 2, 5, 10, 13, 20 ], we get the minimum difference. Our task is to simply return the minimum difference.

Intution

If we sort the array and choose consecutive elements we can get minimum difference of the no of chocolates. So we should sort the array and look at subarray of size m (no of students) that has minimum difference between their first and last element.

Approach

1. Sort the array in ascending order.
2. Initialize the variable minDiff and set its value to INT.MAX
3. Iterate the array where i is the index of current element, m is the total number of students and numberOfStudents is the length of an array
4. For each iteration we are looking at the subarray of size m (no of students). We dont go index out of bound so we use the condition: i + numberOfStudents - 1 < noOfPackets
5. While iterating, we check the difference of first element and last element of that subarray
   1. diff = nums[i + numberOfStudents - 1] - nums[i]
6. If this difference is less than the minDiff, then we store this new diff in our minDiff.
7. Complete the iteration and return the minDiff value.

Complexities:

• Time Complexity: O(N log N), where N is the size of the array
• Space Complexity: O(1)

Java Code:

import java.util.*;

class ChocolateDistribution{

	public int findMinDifference(int nums[], int numberOfStudents) {
		int noOfPackets = nums.length;
		if (numberOfStudents == 0 || noOfPackets == 0)
			return 0;

		Arrays.sort(nums);

		if (noOfPackets < numberOfStudents)
			return -1;

		int minDiff = Integer.MAX_VALUE;

		for (int i = 0; i + numberOfStudents - 1 < noOfPackets; i++) {
			int diff = nums[i + numberOfStudents - 1] - nums[i];
			if (diff < minDiff)
			minDiff = diff;
		}

		return minDiff;
	}


	public static void main(String[] args) {

		int choclateArray[] = { 12, 4, 10, 5, 23, 24, 25, 76, 1, 89, 18, 45, 50 };
		int numberOfStudents = 4; 
		
		ChocolateDistribution minDifference = new ChocolateDistribution();
		System.out.println("Minimum difference is : " + 
           minDifference.findMinDifference(choclateArray, numberOfStudents));

	}

}

Output:

Minimum difference is : 7