# PROBLEM LINK:

Practice

Contest Code Battle 2021.1.2

* Author:* Jaskaran Singh

*Akshit Monga ,Tejus Kaw*

**Tester:***Tejus Kaw*

**Editorialist:**# DIFFICULTY:

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[0]
m = hj[1]
arr=input()
l = list(map(int,arr.split(' ')))
l.sort()
arr = l
minimum = arr[n-1]-arr[0]
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);
int answer = arr[n-1]-arr[0];
for(int i=1;i<m;i++){
int j=n-1+i;
if(j>=m){
break;
}
int k=arr[j]-arr[i];
answer=answer<k?answer:k;
}
cout<<answer<<"\n";
return 0;
}
```