Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 29, 2022 by Ria Pathak






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

NOTE: More than 1 bulb can be placed on the same point of the road.

See original problem statement here

For Example:

Input : N = 7, L = 15
        A[] = [15, 5, 3, 7, 9, 14, 0]

Output : 2.50

Explanation : 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.


I. Consider the gap between 1st bulb placed and starting point of the road.
II. Consider the gap between last built placed and ending point of the road.
III. Consider the gaps between consecutive bulbs placed after sorting the points.

Maximum of Ist gap, IInd gap and (IIIrd gap / 2) will be our desired Result.


  1. Sort all the given bulbs and find out the Maximum Gap between consecutive bulbs one by one, as we need to find the Maximum Radius.
    (Maximum Gap /2) is the Maximum Radius required to fill the light entirely among these bulbs.

  2. 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 :-

  3. The difference between the 0th point on the road and the first position of the bulb in the sorted array i.e. A[0] - 0.

  4. The Lth point and the last bulb position in the sorted array i.e. L - A[L-1]

  5. Take the Maximum out of these two previous values and compare it with the (Maximum Gap /2) value. The Maximum out of these two is our desired result.


A[] = [2, 5]
L = 5

Ist gap   : A[0] - 0    = 2 - 0 = 2
IInd gap  : 5 - A[1]    = 5 - 5 = 0
IIIrd gap : A[1] - A[0] / 2 = (5 - 2)/2 = 3/2 = 1.50 

Maximum (Ist, IInd, IIIrd) = 2

Resultant Radius is 2.00


//Quick Sort has been implemented here for the sake of the problem
void swap(int* a, int* b) 
    int t = *a; 
    *a = *b; 
    *b = t; 
int partition (int arr[], int low, int high)                   /
    int pivot = arr[high]; // pivot 
    int i = (low - 1); // Index of smaller element 

    for (int j = low; j <= high- 1; j++) 
        if (arr[j] < pivot) 
            swap(&arr[i], &arr[j]); 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
void quickSort(int arr[], int low, int high) 
    if (low < high) 
        int pi = partition(arr, low, high); 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 

int main(){

  int t;
    int n,l,m;
      scanf("%d %d",&n,&l);
      int arr[n];
      for(int i=0;i<n;i++) 
      quickSort(arr, 0, n-1);                         
      if(arr[0] > l-arr[n-1])
        m = arr[0]*2;
        m = (l-arr[n-1])*2;
      for(int i=1;i<n;i++) 
      if(arr[i] - arr[i-1] > m)
        m = arr[i] - arr[i-1];
      return 0;

using namespace std;


  int t;cin>>t;
    int n,l,m;
      int arr[n];
      for(int i=0;i<n;i++) cin>>arr[i];
      sort(arr,arr+n);               //inbuilt function for sorting
      m = max(arr[0],l-arr[n-1])*2;
      for(int i=1;i<n;i++) 
        m = max(m,arr[i]-arr[i-1]);

import java.util.*;
import java.util.Arrays;
import java.lang.Math;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(;
    int t = sc.nextInt();
      int n = sc.nextInt();
      int l = sc.nextInt();
      int m;
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
          arr[i] = sc.nextInt();
        Arrays.sort(arr);         //inbuilt function for sorting
        m = Math.max(arr[0],l-arr[n-1])*2;
        for(int i=1;i<n;i++) 
          m = Math.max(m,arr[i]-arr[i-1]);
        System.out.printf("%.2f\n", m/2.0);

Space Complexity: O(1)

[forminator_quiz id="542"]

This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *