Sherlock and MiniMax | HackerRank Solution [Hard]

Problem

Given an integer range, for all M in that inclusive range, determine the minimum: abs(arr[i]-M), for all 
1 <= i <= size[a]
Once that has been determined for all integers in the range, return the M which generated the maximum of those values. If there are multiple M's that result in that value, return the lowest one.

HackerRank Problem Link

Input

The first line contains an integer n, the number of elements in a.
The next line contains n space-separated integers a[i].
The third line contains two space-separated integers p and q, the inclusive endpoints for the range of M.

Output

Print the value of M on a line.

Constraints

• 1 <= n <= 10²
• 1 <= a[i] <= 10⁹
• 1 <= p <= q < 10⁹

Sample Input

3
5 8 14
4 9

Sample Output

4

Solution

Approach: Sort the input array a. After that the required M could either be p, q or lie between the array elements. If a1 and a2 are array elements such that a1 < a2, then possible m could be:

Code Implementation

//
//  main.cpp
//  Sherlock and MiniMax
//
//  Created by Himanshu on 26/03/22.
//


#include <vector>
#include <iostream>
#include <algorithm>
#define MAX_NUM 1000000000
using namespace std;
typedef long long ll;

ll diff, ans = MAX_NUM;

void solve (vector<ll> arr, int n, ll m, ll p, ll q) {
    if (m>=p && m<=q) {
        ll tempDiff = MAX_NUM;
        
        for(int i=0; i<n; i++) {
            tempDiff = min(tempDiff, abs(arr[i]-m));
        }
        
        if(tempDiff > diff || (tempDiff==diff && m<ans)){
            diff = tempDiff;
            ans = m;
        }
    }
}


int main() {
    int n;
    ll p, q;
    cin>>n;
    vector<ll> arr(n);
    
    for (int i=0; i<n; i++) {
        cin>>arr[i];
    }
    
    cin>>p>>q;
    sort(arr.begin(), arr.end());

    solve(arr, n, p, p, q);
    solve(arr, n, q, p, q);
    
    for (int i=1; i<n; i++) {
        solve(arr, n, (arr[i] + arr[i-1])/2, p, q);
    }
    
    cout<<ans<<endl;
    return 0;
}

Time complexity: O(n²), where n is the size of input array

Reference:
YouTube Channel – Algods