# FRSHP - Editorial

Tester: Akshit Monga ,Tejus Kaw
Editorialist: Tejus Kaw

CAKEWALK

# PREREQUISITES:

Basic observations, Sorting

# PROBLEM:

Given M numbers , we have to select N numbers out of that such that the difference between the smallest and the largest in N numbers selected is minimum.

# QUICK EXPLANATION:

From the Question we get the instinct that we need to sort the numbers and find the difference between every N^{th} number and accordingly select N numbers.

# EXPLANATION:

First Sort the numbers and do check the N consecutive integers. Sorting decreases the time complexity from O(M^2) to O(M \cdot logM) of whole question .
The main point in this problem is that we need to check the first N numbers starting from each number i.e. check all tuples of N in sorted order and if there are no N numbers then simply continue that step.

# TIME COMPLEXITY :

• M \cdot Log(M) time for sorting.
• Checking the numbers (M-N)

Therefore total time complexity is O( M \cdot log(M) )

# SOLUTIONS:

Language: C++, Python

Setter's Solution
    p = input()
hj = list(map(int,p.split(' ')))
n = hj
m = hj
arr=input()
l = list(map(int,arr.split(' ')))
l.sort()
arr = l
minimum = arr[n-1]-arr
for i in range(1,m-n+1):
k=arr[i+n-1]-arr[i]
if k<minimum:
minimum=k
print(minimum)

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;std::cin >> n>>m;
int arr[m];
for(int i=0;i<m;i++){
std::cin >> arr[i];
}
sort(arr,arr+m);

for(int i=1;i<m;i++){
int j=n-1+i;
if(j>=m){
break;
}
int k=arr[j]-arr[i];