Hackerrank Angry Children Solution ~ GRK

Hackerrank Angry Children Solution ~ GRK

Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has N packets of candies and would like to distribute one packet to each of the K children in the village (each packet may contain different number of candies). To avoid any fighting among the children, he would like to pick K out of N packets, such that unfairness is minimized.

Suppose the K packets have (x1, x2, x3,....xk) candies in them, where xi denotes the number of candies in the ith packet, then we define unfairness as

max(x1,x2,...xk) - min(x1,x2,...xk)

where max denotes the highest value amongst the elements, and min denotes the least value amongst the elements. Can you figure out the minimum unfairness and print it?

Pre-sort, bookkeeping.
int main() { int N,K; int i,upper,lower[MAX]; scanf("%d %d",&N,&K); for(i = 0;i < N;i++){ scanf("%d",candies + i); } sort(candies,candies+N); int unfairness = candies[K-1]-candies[0]; for(i = 0;i < N-K-1;i++){ if(unfairness>candies[i+K-1]-candies[i]) unfairness = candies[i+K-1]-candies[i]; }

http://www.ideserve.co.in/learn/distribute-chocolates-problem

10	public static void distributeChocolates(int[] chocolatePackets, int n) {
11
12
13	if(chocolatePackets == null || chocolatePackets.length == 0 || n == 0) {
14	return;
15	}
16
17
18	Arrays.sort(chocolatePackets);
19	System.out.println(Arrays.toString(chocolatePackets));
20
21	int m = chocolatePackets.length;
22	if(m < n) {
23	System.out.println("Number of students is more than number of packets. Cannot distribute!" );
24	return;
25	}
26	int minDiff = chocolatePackets[m-1];
27	int first = 0;
28	int last = 0;
29	int diff = 0;
30	for(int i = 0; i + n - 1 < m; i++) {
31	diff = chocolatePackets[i+n-1] - chocolatePackets[i];
32	if(diff < minDiff) {
33	minDiff = diff;
34	first = i;
35	last = i+n-1;
36	}
37	}
38	System.out.println(chocolatePackets[first] + " "  + chocolatePackets[last]);
39	}

Read full article from Hackerrank Angry Children Solution ~ GRK