Light in night

Last Updated on March 29, 2022 by Ria Pathak

CONCEPTS USED:

Sorting

DIFFICULTY LEVEL:

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 0^th point on the road and the first position of the bulb in the sorted array i.e. A[0] - 0.

4. The L^th 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] - 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

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[0] > l-arr[n-1])
        m = arr[0]*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[0],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[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);
        t--;
    }  
  }
}

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