Table of Contents
Sherlock and MiniMax – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Sherlock and MiniMax HackerRank Solution
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
int N, A[1000], P, Q;
int test[100000], test_size;
int check(int k){
int i;
int res = 2000000000;
rep(i,N) res = min(res, abs(A[i]-k));
return res;
}
int main(){
int i, j, k;
int res, mx;
reader(&N);
rep(i,N) reader(A+i);
reader(&P,&Q);
sort(A,A+N);
mx = -1;
test_size = 0;
test[test_size++] = P;
test[test_size++] = Q;
REP(i,1,N) {
k = (A[i] + A[i-1])/2;
if(P<=k && k<=Q) test[test_size++] = k;
k = (A[i] + A[i-1])/2 + 1;
if(P<=k && k<=Q) test[test_size++] = k;
}
sort(test,test+test_size);
mx = -1;
rep(i,test_size){
k = check(test[i]);
if(k > mx) mx = k, res = test[i];
}
writer(res, '\n');
return 0;
}
Java Sherlock and MiniMax HackerRank Solution
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.InputStream;
import java.util.NoSuchElementException;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Egor Kulikov (egor@egork.net)
*/
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
SherlockAndMiniMax solver = new SherlockAndMiniMax();
solver.solve(1, in, out);
out.close();
}
}
class SherlockAndMiniMax {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int count = in.readInt();
int[] array = IOUtils.readIntArray(in, count);
int min = in.readInt();
int max = in.readInt();
int best = -1;
int at = -1;
Arrays.sort(array);
int candidate = Integer.MAX_VALUE;
for (int i : array)
candidate = Math.min(candidate, Math.abs(min - i));
if (candidate > best || candidate == best && at > min) {
at = min;
best = candidate;
}
candidate = Integer.MAX_VALUE;
for (int i : array)
candidate = Math.min(candidate, Math.abs(max - i));
if (candidate > best || candidate == best && at > max) {
at = max;
best = candidate;
}
for (int i = 1; i < count; i++) {
int current = (array[i] + array[i - 1]) / 2;
if (current < min || current > max) {
continue;
}
candidate = current - array[i - 1];
if (candidate > best || candidate == best && at > current) {
at = current;
best = candidate;
}
}
out.printLine(at);
}
}
class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void printLine(int i) {
writer.println(i);
}
}
class IOUtils {
public static int[] readIntArray(InputReader in, int size) {
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}
}
Python 3 Sherlock and MiniMax HackerRank Solution
N = int(input())
A = [int(c) for c in input().split()[:N]]
P, Q = [int(c) for c in input().split()[:2]]
a = sorted(A)
max_point = P
max_distance = min(abs(i - P) for i in a)
for i in range(len(a) - 1):
if a[i] > Q or a[i+1] < P:
continue
m = int((a[i] + a[i+1]) / 2)
if m < P:
point = P
distance = a[i+1] - P
elif m > Q:
point = Q
distance = Q - a[i]
else: #m >= P and m <= Q:
point = m
distance = m - a[i]
if distance > max_distance:
max_point = point
max_distance = distance
point = Q
distance = min(abs(i - Q) for i in a)
if distance > max_distance:
max_point = point
max_distance = distance
print(max_point)
Python 2 Sherlock and MiniMax HackerRank Solution
n = input()
a = sorted(map(int, raw_input().split()))
def f(m):
res = 2e9
for x in a:
res = min(res, abs(x-m))
return res
p,q = map(int, raw_input().split())
res,maks = p,f(p)
for i in xrange(1,n):
m = (a[i]+a[i-1])/2
if m < p or m > q:
continue
if min(m-a[i-1], a[i]-m) > maks:
maks = min(m-a[i-1], a[i]-m)
res = m
elif min(m-a[i-1], a[i]-m) == maks:
res = min(res,m)
if f(q) > maks:
maks = f(q)
res = q
elif f(q) == maks:
res = min(res,q)
print res
C Sherlock and MiniMax HackerRank Solution
#include<stdio.h>
#include<stdlib.h>
void quicksort( long int *x,long int first,long int last){
long int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
long int searchLeft(long int *a,long int N,long int e)
{
long int i=0;
while(a[i]<e && i!=N-1)
i++;
if(a[i]<e) return -1;
else return i;
}
long int searchRight(long int *a,long int N,long int e)
{
long int i=N-1;
while(a[i]>e && i!=0)
i--;
if(a[i]>e) return -1;
else return i;
}
long int min(long int a,long int b)
{
if(a>b)
return b;
else return a;
}
long int func(long int *a,long int N,long int x,long int y,long int l,long int r)
{
long int maxDiff=-1,i,ans;
for(i=x;i<y;i++)
{
long int diff=(a[i+1]-a[i])/2;
if(diff>maxDiff)
{
ans=(a[i+1]+a[i])/2;
maxDiff=diff;
}
}
if(x!=0 && a[x]-a[x-1]>=2*maxDiff && a[x]+a[x-1]>2*l)
{
ans=(a[x]+a[x-1])/2;
maxDiff=(a[x]-a[x-1])/2;
}
if(x==0 && a[x]-l >= maxDiff)
{
ans=l;
maxDiff=a[x]-l;
}
if(x!=0 && min(a[x]-l,l-a[x-1])>=maxDiff)
{
ans=l;
maxDiff=min(a[x]-l,l-a[x-1]);
}
if(y!=N-1 && a[y+1]-a[y]>2*maxDiff && a[y+1]+a[y]<2*r)
{
ans=(a[y]+a[y+1])/2;
maxDiff=(a[y+1]-a[y])/2;
}
if(y==N-1 && r-a[y]>maxDiff)
{
ans=r;
maxDiff=r-a[y];
}
if(y!=N-1 && min(r-a[y],a[y+1]-r)>maxDiff)
ans=r;
return ans;
}
int main()
{
long int N,i,l,r,x,y,ans;
scanf("%ld",&N);
long int a[N];
for(i=0;i<N;i++)
scanf("%ld",a+i);
scanf("%ld %ld",&l,&r);
quicksort(a,0,N-1);
x=searchLeft(a,N,l);
y=searchRight(a,N,r);
if(x==-1)
ans=r;
else if(y==-1)
ans=l;
else
ans=func(a,N,x,y,l,r);
printf("%ld\n",ans);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
