Sherlock and MiniMax Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
it took me long to figure out this problem.
The question requires you to find a point between p and q
if you subtract this from all values of array the minimum absoloute value you get is largest when compared to other minimum values of other points.
when scanning the array(sorted) value between a1 and a2 the value that can be considered is med=(a1+a2)/2 for this point min value will be min(med-a1,med-a2) . all the points after a2 will have more diff simmilary consider for a2 to a3 then a3 to a4.
why median?
see a number line
0-----1----0.5(med)----2-------3
absoloute diff is nothing but distance.
0.5 is has smallest distance from 1 and 2 and it increase for 0 and 3.
now only thing you need to consider is whether median lies between given p and q
Sherlock and MiniMax
You are viewing a single comment's thread. Return to all comments →
it took me long to figure out this problem. The question requires you to find a point between p and q if you subtract this from all values of array the minimum absoloute value you get is largest when compared to other minimum values of other points.
when scanning the array(sorted) value between a1 and a2 the value that can be considered is med=(a1+a2)/2 for this point min value will be min(med-a1,med-a2) . all the points after a2 will have more diff simmilary consider for a2 to a3 then a3 to a4.
why median?
see a number line 0-----1----0.5(med)----2-------3
absoloute diff is nothing but distance.
0.5 is has smallest distance from 1 and 2 and it increase for 0 and 3.
now only thing you need to consider is whether median lies between given p and q