Sherlock and MiniMax | HackerRank Solution [Hard]


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


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.


Print the value of M on a line.


  • 1 <= n <= 102
  • 1 <= a[i] <= 109
  • 1 <= p <= q < 109

Sample Input

5 8 14
4 9

Sample Output



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;
    vector<ll> arr(n);
    for (int i=0; i<n; i++) {
    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);
    return 0;

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

YouTube Channel – Algods

Leave a Reply

Your email address will not be published.