# Minimize Max Distance to Gas Station

[Question] We have an horizontal number line. On that number line, we have gas stations at positions stations, stations, …, stations[N-1], where = size of the stations array. Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized. We have to find the smallest possible value of D. Find the answer exactly to 2 decimal places.

Example 1:

```Input:
N = 10
stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
K = 9
Output: 0.50
Explanation: Each of the 9 stations can be added mid way between all the existing adjacent stations.```

Example 2:

```Input:
N = 10
stations = `[3,6,12,19,33,44,67,72,89,95]`
K = 2
Output: 14.00```
``````// TC: O(Nlog(N))
// SC: O(1)
func isPossibleToPlace(_ stations: [Int],_ x: Double) -> Int {
var station_count = 0
for i in 0..<stations.count - 1 {
let distance = Double(stations[i + 1] - stations[i])
station_count += Int(ceil(distance / x)) - 1
}
return station_count
}

func findSmallestMaxDist(_ stations: [Int], _ k: Int) ->Double {
// Code here
var low = 0.0;
var n = stations.count
var high = Double(stations[n - 1] - stations)
while (high - low) > 0.000001 {
var mid = Double(low + high) / 2
var x = isPossibleToPlace(stations, mid)
if x > k {
low = mid
} else {
high = mid
}
}
return high
}

let gasStationArray = [3,6,12,19,33,44,67,72,89,95]
let gasStationToBeInsert = 2
let gasStationDistance = findSmallestMaxDist(gasStationArray, gasStationToBeInsert)
print(" gasStationDistance -- ", gasStationDistance)// 14``````