# 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.

#### 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 <= 102
• 1 <= a[i] <= 109
• 1 <= p <= q < 109

#### 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:

//
//  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(n2), where n is the size of input array

Reference: