PROBLEM LINK:
Author: Setter’s name
Tester: Tester’s name
DIFFICULTY:
EASY.
Intermediate levels like EASY-MEDIUM is also possible.
PREREQUISITES:
Greedy.
PROBLEM:
The chef has N metal balls and he wants to sell them to gain free money. He found a dealer who wants to buy Metal balls. The dealer has also told Chef that the lesser the difference between the minimum and maximum weight of metal balls, the more money he gets. We have to help a chef to find M metal balls that he has to give to the dealer to gain Maximum money.
QUICK EXPLANATION:
You can simply is check all subsets of size M of a[0…n-1]. For every subset, find the difference between the maximum and minimum elements in it. Finally, return the minimum difference.
EXPLANATION:
Firstly we will sort the array a[0…n-1]. Based on the observations to minimize the difference we require two iterators ie. iterator1 and iterator2. Then we will initialize the iterator1 to 0 and iterator2 to iterator M-1.
Then using for loop you can traverse with the iterator1 and iterator2 initializing the loop from 0. Then we will find the difference between elements at iterator1 and iterator2.
We will store the difference in a variable ANS if it is smaller than ANS . The variable will be initialized by INT_MAX before starting the a for a loop. After every iteration, we will increment the iterator1 and iterator2 by 1. And also after every iteration, we will update the variable ANS by the difference if it is smaller than the ANS.
The value of the variable ANS at the end of the for loop will be the minimum difference.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
int m;
cin>>m;
sort(A,A+n);
int k=0;
int j=m-1;
int maxt=INT_MAX;
while(j<n)
{
if((A[j]-A[k])<maxt)
{
maxt=A[j]-A[k];
}
k++;
j++;;
}
cout<<maxt<<endl;
}
return 0;
}
Tester's Solution
t = int(input())
for x in range(0,t):
n = int(input())
arr = list(map(int,input().split()))
m = int(input())
i = 0
j = m-1
maxn = float("inf")
arr.sort()
while j<n:
if (arr[j]-arr[i]<maxn):
maxn = arr[j]-arr[i]
j=j+1
i=i+1
print(maxn)