{"id":533,"date":"2020-06-11T10:29:42","date_gmt":"2020-06-11T10:29:42","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=533"},"modified":"2022-03-29T00:19:30","modified_gmt":"2022-03-29T00:19:30","slug":"light-in-night","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/light-in-night\/","title":{"rendered":"Light in night"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array A<\/code> containing N<\/code> bulbs placed on the road of length L<\/code>, these bulbs can be placed at any point on the road from (0-L)<\/code>. Every bulb has the same radius of illumination. Your task is to find the Minimum<\/code> radius of the bulb so that the bulbs light up the entire road.<\/p>\n

NOTE<\/em><\/strong>: More than 1<\/code> bulb can be placed on the same point of the road.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : N = 7, L = 15\n        A[] = [15, 5, 3, 7, 9, 14, 0]\n\nOutput : 2.50\n\nExplanation : After sorting all points on road, Maximum gap between any two consecutive points on the road is 5. Also bulbs are placed at 0 and 15 points, so 5\/2 i.e. 2.50 is the radius required to light up the entire road.<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
I. Consider the gap between 1st bulb placed and starting point of the road.\nII. Consider the gap between last built placed and ending point of the road.\nIII. Consider the gaps between consecutive bulbs placed after sorting the points.\n\nMaximum of Ist gap, IInd gap and (IIIrd gap \/ 2) will be our desired Result.<\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. \n
    Sort all the given bulbs and find out the Maximum Gap<\/code> between consecutive bulbs one by one, as we need to find the Maximum Radius<\/code>.
    \n(Maximum Gap<\/code> \/2<\/code>) is the Maximum Radius required to fill the light entirely among these bulbs. <\/p>\n<\/li>\n
  2. \n
    But it is not enough to conclude the results as light has to be also filled on the left side of the first bulb position and on the right side of the last bulb position. So there are two more cases to look into :-<\/p>\n<\/li>\n
  3. \n
    The difference between the 0th<\/sup> point on the road and the first position of the bulb in the sorted array i.e. A[0] - 0<\/code>.<\/p>\n<\/li>\n
  4. \n
    The Lth<\/sup> point and the last bulb position in the sorted array i.e. L - A[L-1]<\/code><\/p>\n<\/li>\n
  5. \n
    Take the Maximum<\/code> out of these two previous values and compare it with the (Maximum Gap<\/code> \/2<\/code>) value. The Maximum<\/code> out of these two is our desired result.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    ILLUSTRATION:<\/h3>\n
    A[] = [2, 5]\nL = 5\n\nIst gap   : A[0] - 0    = 2 - 0 = 2\nIInd gap  : 5 - A[1]    = 5 - 5 = 0\nIIIrd gap : A[1] - A[0] \/ 2 = (5 - 2)\/2 = 3\/2 = 1.50 \n\nMaximum (Ist, IInd, IIIrd) = 2\n\nResultant Radius is 2.00<\/code><\/pre>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t