Problem link:##
Setter: Debjit Datta
Tester: Debjit Datta
Difficulty:##
Easy
Prerequisites:##
sorting, greedy
Explanation:##
Given a number line with n coordinates and m points out of those n points being occupied,
we have to find out a point in the number line such that the minimum distance from that
point to a petrol pump is maximum among all points.
Firstly, we have to sort the input array of m elements. The start will be (arr[0]-0) and end will
be (m-1-arr[m-1]). Then we traverse through the array from i=1 to m-1 and find the minimum
distance among arr[i] and arr[i-1] from their midpoint. The maximum of all these will be our
required answer.
Time Complexity:##
O(m)
Author’s and Tester’s Solution:##
Author’s solution is here