Chef and Laddus For Children Codechef Solution

Chef and Laddus For Children Codechef Solution: Chef has N laddus, i-th of which has a size s_i. There are no two laddues with equal size, i.e. all the laddus have different sizes.

There are K children that came to meet Chef today. Chef wants to give a single laddu to each of these K children. Also, he wants to minimize the difference in the sizes which the children get, i.e. he wants to minimize the maximum difference in the sizes of the laddus distributed. This is because children feel jealous of each other if the other one has a bigger laddu that him/her.

In other words, find a subset of size K which minimizes the value of max_element of the subset – min_element of the subset, and output this minimum difference.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space separated integers N, K.

The second line of each test case contains N space separated denoting the array s

Output

For each test case, output a single integer corresponding to the minimum difference in the sizes of the laddus distributed to the children.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ K ≤ N ≤ 10⁵
• 1 ≤ s_i ≤ 10⁹

Example

Input
3
4 1
3 4 2 5
5 2
1 5 3 7 9
6 3
1 12 7 9 5 17
Output
2
4

Explanation

Example 1. There is only one child, so Chef can give him any laddu. The difference between maximum and minimum size of the laddu will be zero.

Example 2. There are two children now. Chef can give one child a laddu of size 5 and other of 7. The difference between the maximum and minimum size of the laddu will is 2. It’s impossible for Chef to get lower difference between the sizes of laddus.

Example 3. There are three children now. Chef can give one child a laddu of size 5 and other of 7, and the remaining one as 9. The difference between the maximum and minimum size of the laddu will is 4. This is the minimum possible difference between the sizes of laddu that Chef can get.

Chef and Laddus For Children CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
			Scanner s=new Scanner(System.in);
		int t=s.nextInt();
		while(t-->0)
		{
		    int n=s.nextInt();
		    int k=s.nextInt();
		    int[] a=new int[n];
		    for(int i=0;i<n;i++)
		    {
		        a[i]=s.nextInt();
		    }
		    Arrays.sort(a);
		    int d=Integer.MAX_VALUE;
		    for(int i=0;i<n-k;i++)
		    {
		        if(d>(a[i+k-1]-a[i]))
		        {
		            d=a[i+k-1]-a[i];
		        }
		    }
		    System.out.println(d);
		}
	}
}

Chef and Laddus For Children CodeChef Solution in CPP

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
	// your code goes here
	int testCase,n=0,k=0;
	cin>>testCase;
	while(testCase--){
	    cin>>n>>k;
	    int arr[n];
	        for (int i = 0; i < n; i++) {
	            cin>>arr[i];
	        }
	    if(n==1 || k==1){
	        std::cout << "0" << "\n";
	    }else{
	        sort(arr,arr+n);
	        std::vector<int> vct;
	        for (int j = 0; j+k-1 < n; j++) {
	            vct.push_back(arr[j+k-1]-arr[j]);
	        }
	         sort(vct.begin(),vct.end());
	        cout<<vct[0]<<"\n";
	    }
	}
	return 0;
}

Chef and Laddus For Children CodeChef Solution in Python

# cook your dish here
for _ in range(int(input())):
    n,k=map(int,input().split())
    l=list(map(int,input().split()))
    l.sort()
    ans=[]
    for i in range(k-1,n):
        ans.append(l[i]-l[i-(k-1)])
    print(min(ans))

Disclaimer: The above Problem (Chef and Laddus For Children) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.