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[i]). 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 1Function 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 . 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 9Sample Output
4
Explanation
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 1For M = 4, 6, 7, or 9, the result is 1. Since we have to output the smallest of the multiple solutions, we print 4.
Sherlock and MiniMax Solution in java
// SherlockAndMiniMax
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();
}
}