Chef and Laddus For Children Codechef Solution

Hello Programmers In this post, you will know how to solve the Chef and Laddus For Children Codechef Solution.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

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 BrokenProgrammers. This tutorial is only for Educational and Learning purpose.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Memcached Service Codechef Solution