HackerRank Sherlock and MiniMax problem solution

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.

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])

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);
	}
}

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;    
}

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("%dn", res);
    return 0;
}