Chocolate Problem Java

PROGRAM TO SOLVE 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: 

  1. Each student gets one packet.
  2. The difference between the number of chocolates in the packet with maximum chocolates and packet with minimum chocolates given to the students is minimum.


import java.util.*;
 
class MAIN {
     
    // 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
        Arrays.sort(arr);
      
        // Number of students cannot be
        // more than number of packets
        if (n < m)
           return -1;
      
        // Largest number of chocolates
        int min_diff = Integer.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 (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(String[] args)
    {
        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;
        System.out.println("Minimum difference is "
                + findMinDiff(arr, n, m));
             
    }
}

OUTPUT
Minimum difference is 10

Comments

Post a Comment

Popular posts from this blog

Solve the Sudoku Java

PROGRAM TO SOLVE SUDOKU class GFG {      public static boolean isSafe( int [][] board,                                   int row, int col,                                   int num)      {          // Row has the unique (row-clash)          for ( int d = 0 ; d < board.length; d++)          {                             // Check if the number we are trying to   ...
Read more

Jumping Numbers Python

PROGRAM TO PRINT ALL JUMPING NUMBERS SMALLER THAN OR EQUAL TO A GIVEN VALUE class Queue:      def __init__( self ):          self .lst = []          def is_empty( self ):          return self .lst = = []          def enqueue( self , elem):          self .lst.append(elem)          def dequeue( self ):          return self .lst.pop( 0 )     # Prints all jumping numbers smaller than or equal to # x starting with 'num'. It mainly does BFS starting # from 'num'. def bfs(x, num):          # Create a queue and enqueue i to it      q = Queue()      q.enqueue(num)          # Do BFS starting from 1   ...
Read more

Solve the Sudoku Python

PROGRAM TO SOLVE SUDOKU # A Utility Function to print the Grid def print_grid(arr):      for i in range ( 9 ):          for j in range ( 9 ):              print arr[i][j],          print ( 'n' )              # Function to Find the entry in # the Grid that is still  not used # Searches the grid to find an # entry that is still unassigned. If # found, the reference parameters # row, col will be set the location # that is unassigned, and true is # returned. If no unassigned entries # remains, false is returned. # 'l' is a list  variable that has # been passed from the solve_sudoku function # to keep track of incrementation # of Rows and Columns def find_empty_location(arr, l):      for row in range ( 9 ):       ...
Read more