HackerRank ‘Max Min’ / ‘Angry Children’ Solution | MartinKysel.com

HackerRank 'Max Min' / 'Angry Children' Solution | MartinKysel.com

Given a list of N integers, your task is to select K integers from the list such that its unfairnessis minimized.

if (x1,x2,x3,…,xk) are K numbers selected from the list N, the unfairness is defined as

max(x1,x2,…,xk)−min(x1,x2,…,xk)

where max denotes the largest integer among the elements of K, and min denotes the smallest integer among the elements of K.

Pre-sort:
The unfairness is the distance between K elements in a sorted array.

if __name__ == '__main__':

    n = input()

    k = input()

    candies = [input() for _ in range(0,n)]

    candies.sort()

    min_diff = 1000000000

    ## Write code here to compute the answer using (n, k, candies)

    for i in xrange(n - k + 1):

        min_diff = min(min_diff, candies[i+k-1] - candies[i])

     

    print min_diff

Finding a sub list with least max-min difference - Codeforces puzzle
http://comproguide.blogspot.com/2015/02/finding-sub-list-with-least-max-min.html
The solution is to first sort the numbers in ascending order, and move a sliding window of sub-list size from begin to end while keeping track of the minimum difference between first and last numbers of the sub-list.

 sort(sizes.begin(), sizes.end());


 


 int start = 0, end = students-1;


 int minDiff = INT_MAX;


 while( end < list_len )


 {


  minDiff = min(minDiff, sizes[end]-sizes[start]);


  start++;


  end++;


 }


 cout << minDiff << endl;

Read full article from HackerRank 'Max Min' / 'Angry Children' Solution | MartinKysel.com