HackerRank Sherlock and MiniMax Solution

In this post, we will solve 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.
For example, your array arr = [3, 5, 7, 9] and your range is from p = 6 to q = 8 inclusive.

M	|arr[1]-M|	|arr[2]-M|	|arr[3]-M|	|arr[4]-M|	Min
6	   3		   1		   1		   3		 1
7	   4		   2		   0		   2		 0
8	   5		   3		   1		   1

We look at the Min column and see the maximum of those three values is 1. Two M’s
result in that answer so we choose the lower value, 6.
Function Description
Complete the sherlockAndMinimax function in the editor below. It should return an integer as described.
sherlockAndMinimax has the following parameters:

arr: an array of integers
p: an integer that represents the lowest value of the range for M
q: an integer that represents the highest value of the range for M
Input Format
The first line contains an integer n, the number of elements in arr.
The next line contains n space-separated integers arr[i].
The third line contains two space-separated integers p and q, the inclusive endpoints for the range of M.

Output Format

Print the value of M on a line.

Sample Input

3
5 8 14
4 9

Sample Output

M	|arr[1]-M|	|arr[2]-M|	|arr[3]-M|	Min
4	   1		   4		   10		 1
5	   0		   3		    9		 0
6	   1		   2		    8		 1
7	   2		   1		    7		 1
8	   3		   0		    6		 0
9	   4		   1		    5		 1

HackerRank Sherlock and MiniMax Problem Solution

Sherlock and MiniMax C Solution

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


int less(const void* x, const void* y) {
    return (*(int*)x - *(int*)y);
}

int nearest(int* A, int N, int L) {
    int i = 0;
    int curr, next;
    do {
        curr = abs(A[i++] - L);
        next = abs(A[i] - L);
    } while((next < curr) && (i < N));
    return i - 1;
}

int main() {
    int N;
    scanf("%i", &N);

    int* A = (int*)malloc(sizeof(int) * N);

    for (int i = 0; i < N; ++i) {
        scanf("%i", &A[i]);
    }

    int P, Q;
    scanf("%i %i", &P, &Q);

    qsort(A, N, sizeof(int), less);

    int M = A[0];
    int max = 0;

    int start = nearest(A, N, P);
    int finish = nearest(A, N, Q);

    if (abs(P - A[start]) < abs(Q - A[finish])) {
        M = Q;
        max = abs(Q - A[finish]);
    }
    else {
        M = P;
        max = abs(P - A[start]);
    }

    for (int i = start; i < finish; ++i) {
        int L = (A[i + 1] + A[i]) / 2;

        if ((L - A[i] == max) && (L < M)) {
            max = L - A[i];
            M = L;
        }

        if (L - A[i] > max) {
            max = L - A[i];
            M = L;
        }
    }

    printf("%i\n", M);

    free(A);
    return 0;
}

Sherlock and MiniMax C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,p,q;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;++i)    cin>>arr[i];
    cin>>p>>q;
    int ans=-1, most = INT_MIN;
    sort(arr.begin(),arr.end());
    for(int i=0;i<n-1;++i){
        int val = (arr[i+1]+arr[i])/2;
        if(val>=p and val<=q and ((val-arr[i]>most) or (val==most+arr[i] and val<ans))){
            most = val-arr[i];
            ans = val;
        }
        val++;
        if(val>=p and val<=q and (arr[i+1]-val>most or (arr[i+1]==val+most and val<ans))){
            most = arr[i+1] - val;
            ans = val;
        }
    }
    int el[2] = {p,q};
    for(int i=0;i<2;++i){
        int mins = INT_MAX;
        for(int j=0;j<n;++j)
            mins = min(mins,max(el[i],arr[j])-min(el[i],arr[j]));
        if(mins>most or (mins==most and el[i]<ans)){
            most = mins;
            ans = el[i];
        }
    }
    cout<<ans;
    return 0;
}

Sherlock and MiniMax C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        int n = Convert.ToInt32(Console.ReadLine());
        
        string[] tmp = Console.ReadLine().Split();
        
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++)
            a[i] = Convert.ToInt32(tmp[i]);
        
        tmp = Console.ReadLine().Split();
        
        int p = Convert.ToInt32(tmp[0]);
        int q = Convert.ToInt32(tmp[1]);
        
        Array.Sort(a);
        
        int low = 0;
        int high = n - 1;
        
        for (int i = 0; i < n; i++)
        {
            if (p > a[i])
                low = i;
            
            if (q < a[i])
                high = i;
        }
        
        int min = 0;
        int m = p;
        
        if (p < a[0])
        {
            min = a[0] - p;
            m = p;
        }
        
        if (q > a[n - 1])
        {
            if (q - a[n - 1] > min)
            {
                min = q - a[n - 1];
                m = q;
            }
        }
        
        for (int i = low; i < high; i++)
        {
            int diff = (int)((a[i + 1] - a[i]) / 2);
            int mm = (int)((a[i + 1] + a[i]) / 2);
            
            if (mm < p)
            {
                if (p < a[i + 1])
                {
                    diff = a[i + 1] - p;
                
                    if (diff > min)
                    {
                        min = diff;
                        m = p;
                    }
                }
            }
            else if (mm > q)
            {
                if (q > a[i])
                {
                    diff = q - a[i];
                    
                    if (diff > min)
                    {
                        min = diff;
                        m = q;
                    }
                }
            }
            else if (diff > min)            
            {
                m = (int)((a[i + 1] + a[i]) / 2);
                min = (int)((a[i + 1] - a[i]) / 2);
            }
        }
        
        Console.WriteLine(m);
    }
}

Sherlock and MiniMax Java Solution

import java.util.Arrays;
import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] array = new long[n];
        for (int i = 0; i < n; i++)
            array[i] = sc.nextLong();

        long p = sc.nextLong();
        long q = sc.nextLong();

        Arrays.sort(array);

        long res;
        if (array[0] > q)
            res = p;
        else if (array[n - 1] < p)
            res = q;
        else {
            long ans = -1;
            long num = -1;
            if (array[0] > p) {
                if (ans < (array[0] - p)) {
                    ans = (array[0] - p);
                    num = p;
                }
            }

            if (array[n - 1] < q) {
                if (ans < (q - array[n - 1])) {
                    ans = (q - array[n - 1]);
                    num = q;
                }
            }
            for (int i = 0; i < n - 1; i++) {
                long cur = (array[i] + array[i + 1]) / 2;
                if (cur <= q && cur >= p && (cur - array[i]) > ans) {
                    ans = (cur - array[i]);
                    num = cur;
                } else if (cur > q) {
                    if ((q - array[i]) > ans) {
                        ans = (q - array[i]);
                        num = q;
                    }
                } else if (cur < p) {
                    if ((array[i + 1] - p) > ans) {
                        ans = (array[i + 1] - p);
                        num = p;
                    }
                }
            }
            res = num;
        }
        System.out.println(res);
        sc.close();
    }
}

Sherlock and MiniMax JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the sherlockAndMinimax function below.
function sherlockAndMinimax(arr, p, q) {
    var sorted = arr.sort((a, b) => a - b);
    var qualified = [], first = 0, start = 0;
    for (var i = 0; i < sorted.length; i++) {
        var s = sorted[i];
        if (s >= p) {
            if (i == 0) {
                start = i;
                first = s - 2 * (s - p);
            } else {
                var l = sorted[i - 1];
                var mid = l + parseInt((s - l) / 2, 10);
                if (p <= mid) {
                    first = l;
                    start = i;
                } else {
                    first = s - 2 * (s - p);
                    start = i;
                }
            }
            break;
        }
    }
    var last = 0;
    var end = 0;
    for (var i = sorted.length - 1; i >= 0; i--) {
        var s = sorted[i];
        if (s <= q) {
            if (i == sorted.length - 1) {
                end = i;
                last = s + 2 * (q - s);
            } else {
                var r = sorted[i + 1];
                var mid = s + parseInt((r - s) / 2, 10);
                if (q > mid) {
                    last = r;
                    end = i;
                } else {
                    last = s + 2 * (q - s);
                    end = i;
                }
            }
            break;
        }
    }
    var ourArr = [];
    ourArr[ourArr.length] = first;
    for (var i = start; i <= end; i++) {
        ourArr[ourArr.length] = sorted[i];
    }
    ourArr[ourArr.length] = last;
    var maxPoint = getMaxMid(ourArr);
    return maxPoint;

}

function getMaxMid(arr) {
    var maxDiffBy2 = -1;
    var num = -1;
    for (var i = arr.length - 1; i > 0; i--) {
        var diff = arr[i] - arr[i - 1];
        var diffBy2 = parseInt(diff / 2, 10);
        if (maxDiffBy2 < 0) {
            maxDiffBy2 = diffBy2;
            num = arr[i - 1] + diffBy2;
        }
        if (diffBy2 >= maxDiffBy2) {
            maxDiffBy2 = diffBy2;
            num = arr[i - 1] + diffBy2;
        }
    }
    return num;
}


function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine(), 10);

    const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

    const pq = readLine().split(' ');

    const p = parseInt(pq[0], 10);

    const q = parseInt(pq[1], 10);

    let result = sherlockAndMinimax(arr, p, q);

    ws.write(result + "\n");

    ws.end();
}

Sherlock and MiniMax Python Solution

def solve(nval, arr, pval, qval):
    if pval >= qval:
        return pval
    arr.sort()
    mval = 0
    global_maximum = - (10 ** 9 + 1)

    if arr[0] >= pval and global_maximum < (arr[0] - pval):
        global_maximum = arr[0] - pval
        mval = pval

    if arr[-1] <= qval and global_maximum < (qval - arr[-1]):
        global_maximum = qval - arr[-1]
        mval = qval

    for i in range(1, nval):
        tmp = (arr[i] - arr[i - 1]) // 2  # left
        if global_maximum < tmp:
            tmp2 = (arr[i] + arr[i - 1]) // 2  # right
            if pval <= tmp2 <= qval:
                global_maximum = tmp
                mval = tmp2
            else:
                if tmp2 > qval and arr[i - 1] <= qval <= arr[i]:
                    tmp = min(abs(arr[i] - qval), abs(arr[i - 1] - qval))
                    if global_maximum < tmp:
                        global_maximum = tmp
                        mval = qval
                elif tmp2 < pval and arr[i - 1] <= pval <= arr[i]:
                    tmp = min(abs(arr[i] - pval), abs(arr[i - 1] - pval))
                    if global_maximum < tmp:
                        global_maximum = tmp
                        mval = pval
    print(mval)





if __name__ == '__main__':
    nval = int(input())
    arr = list(map(int, input().split()))
    pval, qval = list(map(int, input().split()))
    solve(nval, arr, pval, qval)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python