Tuesday, 23 December 2014

Hackerrank Angry Children Solution

Problem Statement
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?
Input Format
The first line contains an integer N.
The second line contains an integer KN lines follow. Each line contains an integer that denotes the candy in the nth (1nN) packet.
Output Format
An integer that denotes the minimum possible value of unfairness.
Constraints
1<=N<=105
1<=K<=N
0<= number of candies in any packet <=109
Sample Input #00
7
3
10
100
300
200
1000
20
30
Sample Output #00
20
Explanation #00
Here K = 3. We can choose packets that contain 10,20,30 candies. The unfairness is
max(10,20,30) - min(10,20,30) = 30 - 10 = 20
Sample Input #01
10
4
1
2
3
4
10
20
30
40
100
200
Sample Output #01
3
Explanation #01
Here K = 4. We can choose the packets that contain 1,2,3,4 candies. The unfairness is
max(1,2,3,4) - min(1,2,3,4) = 4 - 1 = 3

Source Code:

 #include <stdio.h>  
 #include <string.h>  
 #include <math.h>  
 #include <stdlib.h>  
 #include <algorithm>  
 using namespace std;  
 #define MAX 100000  
 #define MAX_VAL 1000000001  
 int candies[MAX];  
 int cmpfunc (const void * a, const void * b)  
 {  
   return ( *(int*)a - *(int*)b );  
 }  
 /** The code to read from STDIN and output to STDOUT has been provided by us, for convenience. You may or may not use this. **/  
 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];  
 }  
   // Compute the min unfairness over here, using N,K,candies  
   printf("%d\n",unfairness);  
   return 0;  
 }  



** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)


2 comments:

  1. import java.util.*;
    import java.math.*;

    public class Solution {
    public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    long[] packets = new long[n];
    long min;
    for(int i = 0; i < n; i ++)
    {
    packets[i] = in.nextInt();
    }
    Arrays.sort(packets);
    min = packets[k -1] - packets[0];
    for(int i = 1; i < n - k + 1; i++)
    {
    if(min > (packets[k + i - 1] - packets[i]))
    min = packets[k + i - 1] - packets[i];
    }
    System.out.println(min);
    }
    }

    ReplyDelete
    Replies
    1. vai jhere kano post korchhis

      Delete