29. Chocolate distribution problem

29. Chocolate distribution problem

Problem link :- click here

\

package programs;

import java.util.*;

public class Array__29
{

	/*
	    we will sort the array first and take every possible sub-array of size 'm'
	    and since we have already sorted the array. 
	    we can get the minimum and maximum of that sub-array easily.
	    we will return minimum of these values.
	 */
	static int minDifference(int arr[], int n, int m)
	{
		/*
		    sorting the array using 
		    class ------>  Arrays (which is a member of  Java Collections Framework)
		    method -->   sort()
		*/
		Arrays.sort(arr);
		
		int min_difference = Integer.MAX_VALUE;
		/*
		     we already know the size of the sub-array i.e., m.
		     and we are iterating from 'i' which means 'i' is our first element's index
		     so our last element's index will be (m+i-1)
		     for loop condition will be if the last element of the sub-array is present
		*/
		for(int i=0; (m+i-1)<n; i++)
		{
			//updating min_difference
			int diff = arr[m+i-1] - arr[i];
			min_difference = Math.min(min_difference, diff);
		}
		
		return min_difference;
	}
	
	public static void main(String[] args)
	{
		int i, n, m, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.print("Enter the number of students : ");
		m = s.nextInt();
		
		System.out.println("Given Array : ");
		print_array(array);
		
		ans = minDifference(array, n, m);
		System.out.println("\n\nMinimum differenece is : " + ans);
	}

	static void print_array(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n*log(n))
Space complexity :- O(1)