Efficient Approach for Chocolate Distribution Problem
The idea is based on the observation that to minimize the difference, we must choose consecutive elements from a sorted packet. We first sort the array arr[0..n-1], then find the subarray of size m with the minimum difference between the last and first elements.
Illustration:
Below is the illustration of example arr[] = [ 7,3,2,4,9,12,56 ] , m = 3
Follow the steps mentioned below to implement the approach:
- Initially sort the given array. And declare a variable to store the minimum difference, and initialize it to INT_MAX. Let the variable be min_diff.
- Find the subarray of size m such that the difference between the last (maximum in case of sorted) and first (minimum in case of sorted) elements of the subarray is minimum.
- We will run a loop from 0 to (n-m), where n is the size of the given array and m is the size of the subarray.
- We will calculate the maximum difference with the subarray and store it in diff = arr[highest index] – arr[lowest index]
- Whenever we get a diff less than the min_diff, we will update the min_diff with diff.
Below is the implementation of the above approach:
C++
// C++ program to solve chocolate distribution // problem #include <bits/stdc++.h> using namespace std; // arr[0..n-1] represents sizes of packets // m is number of students. // Returns minimum difference between maximum // and minimum values of distribution. int findMinDiff( int arr[], int n, int m) { // if there are no chocolates or number // of students is 0 if (m == 0 || n == 0) return 0; // Sort the given packets sort(arr, arr + n); // Number of students cannot be more than // number of packets if (n < m) return -1; // Largest number of chocolates int min_diff = INT_MAX; // Find the subarray of size m such that // difference between last (maximum in case // of sorted) and first (minimum in case of // sorted) elements of subarray is minimum. for ( int i = 0; i + m - 1 < n; i++) { int diff = arr[i + m - 1] - arr[i]; if (diff < min_diff) min_diff = diff; } return min_diff; } int main() { int arr[] = { 12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50 }; int m = 7; // Number of students int n = sizeof (arr) / sizeof (arr[0]); cout << "Minimum difference is " << findMinDiff(arr, n, m); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to solve chocolate distribution problem #include <limits.h> #include <stdio.h> #include <stdlib.h> // Compare function for qsort int cmpfunc( const void * a, const void * b) { return (*( int *)a - *( int *)b); } // arr[0..n-1] represents sizes of packets // m is number of students. // Returns minimum difference between maximum // and minimum values of distribution. int findMinDiff( int arr[], int n, int m) { // if there are no chocolates or number // of students is 0 if (m == 0 || n == 0) return 0; // Sort the given packets qsort (arr, n, sizeof ( int ), cmpfunc); // Number of students cannot be more than // number of packets if (n < m) return -1; // Largest number of chocolates int min_diff = INT_MAX; // Find the subarray of size m such that // difference between last (maximum in case // of sorted) and first (minimum in case of // sorted) elements of subarray is minimum. for ( int i = 0; i + m - 1 < n; i++) { int diff = arr[i + m - 1] - arr[i]; if (diff < min_diff) min_diff = diff; } return min_diff; } int main() { int arr[] = { 12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50 }; int m = 7; // Number of students int n = sizeof (arr) / sizeof (arr[0]); printf ( "Minimum difference is %d" , findMinDiff(arr, n, m)); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// JAVA Code For Chocolate Distribution Problem import java.util.Arrays; public class ChocolateDistribution { /** * Calculates the minimum difference between the maximum and minimum chocolates * received by any student after distributing chocolates in packets. * * @param arr Array representing sizes of chocolate packets. * @param m Number of students. * @return Minimum difference between maximum and minimum chocolates. */ public static int chocolateDistribution( int arr[], int m) { // Check base cases if (arr.length == 0 || m == 0 ) { return 0 ; } // Sort the array to simplify calculations Arrays.sort(arr); // Check if there are enough packets for the given number of students if (arr.length - 1 < m) { // Invalid input return - 1 ; } // Initialize minimum difference to the maximum possible integer value int min_diff = Integer.MAX_VALUE; // Iterate through the array to find the minimum difference for ( int i = 0 ; i < arr.length; i++) { // Calculate the ending index of the current window int nextWindow = i + m - 1 ; // Break if the window goes beyond the bounds of the array if (nextWindow >= arr.length) break ; // Calculate the difference between the last and first elements in the window int diff = arr[nextWindow] - arr[i]; // Update the minimum difference if a smaller difference is found min_diff = Math.min(min_diff, diff); } // Return the calculated minimum difference return min_diff; } public static void main(String[] args) { // Example input int arr[] = { 12 , 4 , 7 , 9 , 2 , 23 , 25 , 41 , 30 , 40 , 28 , 42 , 30 , 44 , 48 , 43 , 50 }; int m = 7 ; // Calculate the result using the chocolateDistribution method int result = chocolateDistribution(arr, m); // Print the result or indicate an invalid input if (result != - 1 ) { System.out.println( "Minimum difference is " + result); } else { System.out.println( "Invalid input" ); } } } |
Python3
# Python3 program to solve # chocolate distribution # problem # arr[0..n-1] represents sizes of packets # m is number of students. # Returns minimum difference between maximum # and minimum values of distribution. def findMinDiff(arr, n, m): # if there are no chocolates or number # of students is 0 if (m = = 0 or n = = 0 ): return 0 # Sort the given packets arr.sort() # Number of students cannot be more than # number of packets if (n < m): return - 1 # Largest number of chocolates min_diff = arr[n - 1 ] - arr[ 0 ] # Find the subarray of size m such that # difference between last (maximum in case # of sorted) and first (minimum in case of # sorted) elements of subarray is minimum. for i in range ( len (arr) - m + 1 ): min_diff = min (min_diff, arr[i + m - 1 ] - arr[i]) return min_diff # Driver Code if __name__ = = "__main__" : arr = [ 12 , 4 , 7 , 9 , 2 , 23 , 25 , 41 , 30 , 40 , 28 , 42 , 30 , 44 , 48 , 43 , 50 ] m = 7 # Number of students n = len (arr) print ( "Minimum difference is" , findMinDiff(arr, n, m)) # This code is contributed by Smitha |
C#
// C# Code For Chocolate Distribution // Problem using System; class GFG { // arr[0..n-1] represents sizes of // packets. m is number of students. // Returns minimum difference between // maximum and minimum values of // distribution. static int findMinDiff( int [] arr, int n, int m) { // if there are no chocolates or // number of students is 0 if (m == 0 || n == 0) return 0; // Sort the given packets Array.Sort(arr); // Number of students cannot be // more than number of packets if (n < m) return -1; // Largest number of chocolates int min_diff = int .MaxValue; // Find the subarray of size m // such that difference between // last (maximum in case of // sorted) and first (minimum in // case of sorted) elements of // subarray is minimum. for ( int i = 0; i + m - 1 < n; i++) { int diff = arr[i + m - 1] - arr[i]; if (diff < min_diff) min_diff = diff; } return min_diff; } /* Driver program to test above function */ public static void Main() { int [] arr = { 12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50 }; int m = 7; // Number of students int n = arr.Length; Console.WriteLine( "Minimum difference is " + findMinDiff(arr, n, m)); } } // This code is contributed by vt_m. |
Javascript
<script> // Javascript Code For Chocolate // Distribution Problem // arr[0..n-1] represents sizes of // packets. m is number of students. // Returns minimum difference between // maximum and minimum values of // distribution. function findMinDiff(arr, n, m) { // If there are no chocolates or // number of students is 0 if (m == 0 || n == 0) return 0; // Sort the given packets arr.sort( function (a, b){ return a - b}); // Number of students cannot be // more than number of packets if (n < m) return -1; // Largest number of chocolates let min_diff = Number.MAX_VALUE; // Find the subarray of size m // such that difference between // last (maximum in case of // sorted) and first (minimum in // case of sorted) elements of // subarray is minimum. for (let i = 0; i + m - 1 < n; i++) { let diff = arr[i + m - 1] - arr[i]; if (diff < min_diff) min_diff = diff; } return min_diff; } // Driver code let arr = [ 12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50 ]; // Number of students let m = 7; let n = arr.length; document.write( "Minimum difference is " + findMinDiff(arr, n, m)); // This code is contributed by divyesh072019 </script> |
PHP
<?php // PHP program to solve // chocolate distribution // problem // arr[0..n-1] represents // sizes of packets m is // number of students. // Returns minimum difference // between maximum and minimum // values of distribution. function findMinDiff( $arr , $n , $m ) { // if there are no // chocolates or number // of students is 0 if ( $m == 0 || $n == 0) return 0; // Sort the given packets sort( $arr ); // Number of students // cannot be more than // number of packets if ( $n < $m ) return -1; // Largest number // of chocolates $min_diff = PHP_INT_MAX; // Find the subarray of size // m such that difference // between last (maximum in // case of sorted) and first // (minimum in case of sorted) // elements of subarray is minimum. for ( $i = 0; $i + $m - 1 < $n ; $i ++) { $diff = $arr [ $i + $m - 1] - $arr [ $i ]; if ( $diff < $min_diff ) $min_diff = $diff ; } return $min_diff ; } // Driver Code $arr = array (12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50); $m = 7; // Number of students $n = sizeof( $arr ); echo "Minimum difference is " , findMinDiff( $arr , $n , $m ); // This code is contributed by ajit ?> |
Minimum difference is 10
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Chocolate Distribution Problem
Given an array of N integers 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 such that:
- Each student gets one packet.
- The difference between the number of chocolates in the packet with maximum chocolates and the packet with minimum chocolates given to the students is minimum.
Examples:
Input : arr[] = {7, 3, 2, 4, 9, 12, 56} , m = 3
Output: Minimum Difference is 2
Explanation:
We have seven packets of chocolates and we need to pick three packets for 3 students
If we pick 2, 3 and 4, we get the minimum difference between maximum and minimum packet sizes.Input : arr[] = {3, 4, 1, 9, 56, 7, 9, 12} , m = 5
Output: Minimum Difference is 6Input : arr[] = {12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50} , m = 7
Output: Minimum Difference is 10
Contact Us