Chocolate Distribution Problem

Given an array A[ ] of positive integers of size N, 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 among M students such that :

1. Each student gets exactly one packet.
2. The difference between a maximum number of chocolates given to a student and a minimum number of chocolates given to a student is minimum.

Input Format

The first line contains an integer N and M, N represents the number of chocolate packets and M represents the number of students. The second line contains n integers a1, a2, … the array elements themselves.

Output Format

Print the minimum possible difference between a maximum number of chocolates given to a student and a minimum number of chocolates given to a student.

Example 1:

Input:
    8 5
    3 4 1 9 56 7 9 12
Output:
    6
Explanation:
    The minimum difference between
    maximum chocolates and minimum chocolates
    is 9 - 3 = 6 by choosing following M packets :
    {3, 4, 9, 7, 9}.

Example 2:

Input:
    7 3
    7 3 2 4 9 12 56
Output:
    2
Explanation:
    The minimum difference between
    maximum chocolates and minimum chocolates
    is 4 - 2 = 2 by choosing following M packets :
    {3, 2, 4}.

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100000
• 1 ≤ A[i] ≤ 1000000000
• 1 ≤ M ≤ N
• Expected Time Complexity: O(N*Log(N))
• Expected Auxiliary Space: O(1)