FRSHP - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest Code Battle 2021.1.2

Author: Jaskaran Singh
Tester: Akshit Monga ,Tejus Kaw
Editorialist: Tejus Kaw

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;
}
1 Like