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