CYPH2021: Editorial

editorial
, , ,
1

CONTEST CODE : CYPH2021

PROBLEM LINK : CodeChef: Practical coding for everyone

PROBLEM CODE : MINHIG

Author: Avdhoot Ubale

Tester: Avdhoot Ubale

Editorialist: Avdhoot Ubale

DIFFICULTY : Easy

PREREQUISITES : Array/Vectors, Sorting, Implementation Skills

PROBLEM :

Given an Array of heights of boxes we need to find pairs of boxes with minimum difference between their heights

EXPLANATION :

The naive solution for this problem is to use two loops. For every number a[i], loop over all the numbers to find the optimum number b[i] where (a[i] - b[i]) is minimum. Then, choose the minimum value among all the pairs. This solution has a time complexity O(N2) which will cause the Time Limit Exceeded issue. Therefore, you need to think in another way to find the closest number.

Sort the input array in ascending order. The closest number b[i] to a number a[i] will be either the number before or after it in the list. Calculate the difference between every successive pair and find the minimum value of the difference.

Again loop through the array to print those pairs whose difference between heights is minimum.

Time Complexity: O(N*logN)
Space Complexity: O(N)

Solution:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,p;
    cin>>n;
    vector<int>a;
    
    for(int i=0;i<n;i++){
        cin>>p;
        a.push_back(p);
    }

    sort(a.begin(),a.end());
    int min=abs(a[0]-a[1]);

    for(int i=0;i<n-1;i++){
        if(abs(a[i]-a[i+1])<min){
            min=abs(a[i]-a[i+1]);
        }
    }

    for(int i=0;i<n-1;i++){
        if(abs(a[i]-a[i+1])==min){
            cout<<a[i]<<" "<<a[i+1]<<" ";
        }
    }
    return 0;
}