PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : BEGINNER
PREREQUISITES:
Nill
PROBLEM:
There are N horses in the stable. The skill of the horse i is represented by an integer S[i]. The Chef needs to pick 2 horses such that the difference in their skills is minimum. Your task is to help him do this and report the minimum difference that is possible between 2 horses in the race.
QUICK EXPLANATION:
We can find the solution by sorting the array S, and finding the minimum difference among two consecutive elements.
EXPLANATION:
First, we should get the required input from the user and store the numbers in an array. Let’s name it S.
Since we should find the minimum difference possible, it would be easier if we sort the array.
Why sorting?
Consider two elements S[i] and S[j], and let S[i]<=S[j]. Then if S[j] - S[i] is the minimum difference, then there should not exist an element S[k], such that S[i] < S[k] < S[j]. If such an element exists, then S[k] - S[i] is lesser than S[j] - S[i]. Which means that the difference between S[k] and S[i] is lesser than that of S[j] and S[i] and thus, S[j] - S[i] is no longer the minimum difference possible. So if S[i] - S[j] is the minimum difference possible, then there should not exist an element S[k]. So by sorting, we can arrange all the elements in such a manner that for any consecutive elements, there does not exist an element which is greater than the first element and lesser than the second.
So we sorted the elements in ascending (or descending) order. Now instead of going through all possible pairs, we just have to iterate and look through the differences of consecutive elements.
SOLUTIONS:
Setter's Solution
using namespace std;
int main() {
int T;
cin>>T;
while(T>0)
{
int n;
cin>>n;
int ar[n];
for(int i=0;i<n;i++)
{
cin>>ar[i];
}
sort(ar,ar+n); // sort function from C++ STL
int min=ar[n-1];
for(int i=0;i<n-1;i++)
{
if(ar[i+1]-ar[i]<min)
min=ar[i+1]-ar[i];
}
cout<<min<<“\n”;
T–;
}
return 0;
}
Tester's Solution
Same Person
Editorialist's Solution
Same Person