In this HackerRank Sherlock and MiniMax problem solution Watson gives Sherlock an array of integers. Given the endpoints of an integer range, for all M in that inclusive range, determine the minimum( abs(arr[i]-M) for all 1 <= i <= |arr| ) ). 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 Sherlock and MiniMax problem solution


Problem solution in Python.

n = int(input())
a = list(sorted(map(int, input().split())))
p, q = map(int, input().split())
def f(m):
    if m < p or m > q: return 0
    r = 1 << 32
    for i in a: r = min(r, abs(i - m))
    return r
ans = max((f(p), -p), (f(q), -q))
for i in range(1, n):
    m = (a[i] + a[i - 1]) // 2
    ans = max(ans, (f(m), -m))
print(-ans[1])

{"mode":"full","isActive":false}


Problem solution in Java.

import java.io.*;
import java.util.Arrays;



public class Solution {
	public static void main(String[] args) throws IOException {
		int N;
		long[] A;
		long P, Q;
		BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(bi.readLine().trim());
		A = new long[N];
		String[] inStr = bi.readLine().trim().split("\\s+");
		for(int i=0;i<N;i++) 
			A[i] = Long.parseLong(inStr[i]);
		inStr = bi.readLine().trim().split("\\s+");
		P = Long.parseLong(inStr[0]);
		Q = Long.parseLong(inStr[1]);
		Arrays.sort(A);
		long maxDist = 0;
		long maxLoc = Long.MAX_VALUE;
		if(P <= A[0]) {
			maxDist = A[0] - P;
			maxLoc = P;
		}
		if(Q >= A[N-1]){
			if(Q - A[N-1] > maxDist) {
				maxDist = Q - A[N-1];
				maxLoc = Q;
			}
		}
		for(int i=0;i<N-1;i++){
			if(P >= A[i] && P <= A[i+1]) {
				long minD = Math.min(P - A[i], A[i+1] - P);
				if (minD > maxDist) {
					maxDist = minD;
					maxLoc = P;
				}
				else if(minD == maxDist)
					maxLoc = Math.min(maxLoc, P);
			}
			if(Q >= A[i] && Q <= A[i+1]) {
				long minD = Math.min(Q - A[i], A[i+1] - Q);
				if (minD > maxDist) {
					maxDist = minD;
					maxLoc = Q;
				}
				else if(minD == maxDist)
					maxLoc = Math.min(maxLoc, Q);
			}
			long midPt = (A[i+1] + A[i])/2;
			if(Q >= midPt && P <= midPt) {
				long minD = Math.min(midPt - A[i], A[i+1] - midPt);
				if (minD > maxDist) {
					maxDist = minD;
					maxLoc = midPt;
				}
				else if(minD == maxDist)
					maxLoc = Math.min(maxLoc, midPt);
			}
			if(Q >= (midPt + 1) && P <= (midPt + 1) && (midPt + 1 <= A[i+1])) {
				long minD = Math.min(midPt + 1 - A[i], A[i+1] - midPt - 1);
				if (minD > maxDist) {
					maxDist = minD;
					maxLoc = midPt;
				}
				else if(minD == maxDist)
					maxLoc = Math.min(maxLoc, midPt + 1);
			}
		}

		System.out.println(maxLoc);
	}
}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
int n;
vector<long long> vt;
long long x;
long long f,l;
long long check(long long t){
    long long res = 1000000000L*10000000;
    for(int i=0; i<vt.size(); i++)
        res = min(res, abs(vt[i]-t));
    return res;
}

int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%lld",&x);
        vt.push_back(x);
    }
    scanf("%lld %lld",&f, &l);
    sort(vt.begin(),vt.end());
    long long r=f;
    long long res = check(f);
    
    for(int i=1; i<vt.size(); i++){
        long long m = (vt[i] + vt[i-1])/2;
        if( f<= m && l>= m){
            long long temp = check(m);
            if(res < temp){
                res=temp;
                r=m;
            }
        }            
        if( f<= m+1 && l>= m+1){
            long long temp = check(m+1);
            if(res < temp){
                res=temp;
                r=m+1;
            }
        }            
    }    
    if(res < check(l))
        r=l;
    cout << r << endl;
    return 0;    
}

{"mode":"full","isActive":false}


Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int n, *a, p, q;
    int i, res, tmpMax, tmp, curMax;
    scanf("%d", &n);
    a = (int *) malloc(sizeof(int) * n);
    for(i = 0;i < n;++i){
        scanf("%d", a + i);
    }
    scanf("%d", &p);
    scanf("%d", &q);
    
    // sort first
    int bSomeChange = 0;
    do{
        bSomeChange = 0;
        for(i = 0;i < n - 1;++i){
            if(a[i] > a[i + 1]){
                tmp = a[i];
                a[i] = a[i+1];
                a[i+1] = tmp;
                bSomeChange = 1;
            }
        }
    }while(bSomeChange != 0);
    //
    
    res = tmpMax = -1;
    
    if(p < a[0]){
        res = p;
        tmpMax = a[0] - p;
    }
    else if(p >= a[n-1]){
        res = q;
        tmpMax = q - a[n-1];
    }
    if (q > a[n-1] && q - a[n-1] > tmpMax){
        res = q;
        tmpMax = q - a[n-1];
    }
    for (i = 0;i < n - 1;++i){
        // printf("%d ", a[i]);
        if(p > a[i + 1]) continue;
        if (q < a[i])
            break;
        tmp = (a[i + 1] + a[i]) / 2;
        if (tmp > q) {
            tmp = q;
            curMax = tmp - a[i];
        }
        else if (tmp < p) {
            tmp = p;
            curMax = a[i+1] - tmp;
        }
        else{
            curMax = tmp - a[i];
        }
        if (curMax > tmpMax){
            tmpMax = curMax;
            res = tmp;
        }
    }
    
    free(a);
    
    printf("%d\n", res);
    return 0;
}

{"mode":"full","isActive":false}