HackerRank: Sherlock and MiniMax
Watson gives Sherlock an array A1,A2...AN.
He asks him to find an integer M between P and Q(both inclusive), such that, min {|Ai-M|, 1 ≤ i ≤ N} is maximised. If there are multiple solutions, print the smallest one.
Solution: M will be either A or B or (A_i+A_j)/2. We check for each pair and store if the answer is minimum. See setter's solution for more details.
There is an O(n log(n)) solution to this problem. First you sort the the input, the answer would be P, Q or a point in the middle of x[i] and x[i-1], the point is that maybe MID = (x[i]+x[i-1])/2 is not in range [P, Q], then you have to find the closest point to MID in range (x[i-1], x[i]) which is also in range [P, Q]. (you need to look at the intersection of two ranges, [x[i-1], x[i]] and [P, Q]).
https://codepair.hackerrank.com/paper/aQcOdMbX?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int a[] = new int[n];
for (int i=0; i<n; i++) a[i] = cin.nextInt();
int p = cin.nextInt(), q = cin.nextInt();
Arrays.sort(a);
List<Integer> cb = new ArrayList<Integer>();
for (int i=0; i+1<n; i++) {
if ((a[i] + a[i + 1]) % 2 == 0) cb.add((a[i] + a[i + 1]) / 2);
else {
// optimize: don't add it if the value is not in range p and q
cb.add((a[i] + a[i + 1]) / 2);
cb.add((a[i] + a[i + 1]) / 2 + 1);
}
}
cb.add(p);
cb.add(q);
Collections.sort(cb);
long da = -1;
long ans = 0;
for (int i : cb) {
if (i >= p && i <= q) {
long min = Long.MAX_VALUE;
for (int j : a)
min = Math.min(min, Math.abs(0L + i - j));
if (min > da) {
da = min;
ans = i;
}
}
}
System.out.println(ans);
cin.close();
}
Watson gives Sherlock an array A1,A2...AN.
He asks him to find an integer M between P and Q(both inclusive), such that, min {|Ai-M|, 1 ≤ i ≤ N} is maximised. If there are multiple solutions, print the smallest one.
Solution: M will be either A or B or (A_i+A_j)/2. We check for each pair and store if the answer is minimum. See setter's solution for more details.
There is an O(n log(n)) solution to this problem. First you sort the the input, the answer would be P, Q or a point in the middle of x[i] and x[i-1], the point is that maybe MID = (x[i]+x[i-1])/2 is not in range [P, Q], then you have to find the closest point to MID in range (x[i-1], x[i]) which is also in range [P, Q]. (you need to look at the intersection of two ranges, [x[i-1], x[i]] and [P, Q]).
https://codepair.hackerrank.com/paper/aQcOdMbX?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int a[] = new int[n];
for (int i=0; i<n; i++) a[i] = cin.nextInt();
int p = cin.nextInt(), q = cin.nextInt();
Arrays.sort(a);
List<Integer> cb = new ArrayList<Integer>();
for (int i=0; i+1<n; i++) {
if ((a[i] + a[i + 1]) % 2 == 0) cb.add((a[i] + a[i + 1]) / 2);
else {
// optimize: don't add it if the value is not in range p and q
cb.add((a[i] + a[i + 1]) / 2);
cb.add((a[i] + a[i + 1]) / 2 + 1);
}
}
cb.add(p);
cb.add(q);
Collections.sort(cb);
long da = -1;
long ans = 0;
for (int i : cb) {
if (i >= p && i <= q) {
long min = Long.MAX_VALUE;
for (int j : a)
min = Math.min(min, Math.abs(0L + i - j));
if (min > da) {
da = min;
ans = i;
}
}
}
System.out.println(ans);
cin.close();
}
