# Light in night Sorting

Medium

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

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.``````

### OBSERVATION:

``````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.``````

### SOLVING APPROACH:

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`.

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.

### ILLUSTRATION:

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

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

Maximum (Ist, IInd, IIIrd) = 2

### SOLUTIONS:

```#include<stdio.h>
//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)
{
i++;
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;
scanf("%d",&t);
while(t--)
{
int n,l,m;
scanf("%d %d",&n,&l);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
quickSort(arr, 0, n-1);
if(arr > l-arr[n-1])
m = arr*2;
else
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];
printf("%.2f\n",m/2.0);
return 0;
}
}

```
```#include<bits/stdc++.h>
using namespace std;

main(){

int t;cin>>t;
while(t--)
{
int n,l,m;
cin>>n>>l;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
sort(arr,arr+n);               //inbuilt function for sorting
m = max(arr,l-arr[n-1])*2;
for(int i=1;i<n;i++)
m = max(m,arr[i]-arr[i-1]);
cout<<fixed<<setprecision(2)<<m/2.0<<"\n";
}
}

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

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

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t!=0)
{
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,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);
t--;
}
}
}

```

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.