Program to find minimum radius to light up all houses on a street in Python

Suppose we have a list of numbers called nums that are representing position of houses on a 1-dimensional line. Now consider we have 3 street lights that we can put anywhere on the line and a light at position x lights up all houses in range [x - r, x + r], inclusive. We have to find the smallest r required to light up all houses.

So, if the input is like nums = [4,5,6,7], then the output will be 0.5, as we can place the lamps on 4.5, 5.5 and 6.5 so r = 0.5. So these three lights can light up all 4 houses.

To solve this, we will follow these steps −

• Define a function valid() . This will take r

• last_location := nums[0] + r

• count := 1

• for i in range 0 to size of nums, do

  • val := nums[i]

  • if val - last_location > r, then

    • count := count + 1

    • last_location := val + r

• return true when count <= 3, otherwise false

• From the main method do the following −

• sort the list nums

• left := 0

• right := last element of nums

• res := inf

• itr := 0

• while left <= right and itr < 20, do

  • mid := left +(right - left) / 2

  • if valid(mid) is true, then

    • res := minimum of res and mid

    • right := mid

  • otherwise,

    • left := mid

    • itr := itr + 1

• return res

Example 

Let us see the following implementation to get better understanding −

 Live Demo

class Solution:    def solve(self, nums):       def valid(r):          last_location = nums[0] + r          count = 1          for i in range(len(nums)):             val = nums[i]             if val - last_location > r:                count += 1                last_location = val + r          return count <= 3       nums.sort()       left = 0       right = nums[-1]       res = float("inf")       itr = 0       while left <= right and itr < 20:          mid = left + (right - left) / 2          if valid(mid):             res = min(res, mid)             right = mid          else:             left = mid          itr += 1       return res ob = Solution() nums = [4,5,6,7] print(ob.solve(nums))

Input

[4,5,6,7]

Output

0.5