We have an horizontal number line. On that number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = 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
Explanation: Construction of gas stations at 86 locations
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findSmallestMaxDist() which takes a list of stations and integer K as inputs and returns the smallest possible value of D. Find the answer exactly to 2 decimal places.
Expected Time Complexity: O(N*log K)
Expected Auxiliary Space: O(1)
Constraint:
10 <= N <= 5000^{ }
0 <= stations[i] <= 10^{9 }
0 <= K <= 10^{5}
stations is sorted in a strictly increasing order.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: #User function Template for python3



class Solution:

    def findSmallestMaxDist(self, stations, K):

        # Code here

Solutions:
class Solution:

	def findSmallestMaxDist(self, stations, K):
		(start, end) = (0, stations[-1] - stations[0])
		while end - start > 1e-05:
			mid = (start + end) / 2
			if self.isPossible(stations, K, mid):
				end = mid
			else:
				start = mid
		return end

	def isPossible(self, stations, k, maxDist):
		stationsToAdd = 0
		for i in range(1, len(stations)):
			stationsToAdd += (stations[i] - stations[i - 1]) // maxDist
		return stationsToAdd <= k


class Solution:

	def ok(self, a, n, d, k):
		cnt = 0
		for i in range(1, n):
			cnt += (a[i] - a[i - 1]) // d
		return cnt <= k

	def findSmallestMaxDist(self, stations, K):
		(lo, hi) = (0, stations[-1])
		n = len(stations)
		ans = hi
		eps = 1e-06
		while hi - lo > eps:
			mi = (lo + hi) / 2
			if self.ok(stations, n, mi, K):
				ans = mi
				hi = mi
			else:
				lo = mi
		return ans


class Solution:

	def findSmallestMaxDist(self, stations, K):
		n = len(stations)
		(i, j) = (0, stations[-1] - stations[0])
		while j - i > 1e-06:
			m = (i + j) / 2
			c = 0
			for x in range(1, n):
				c += int((stations[x] - stations[x - 1]) / m)
			if c <= K:
				j = m
			else:
				i = m
		return j


class Solution:

	def findSmallestMaxDist(self, stations, K):
		(left, right) = (1e-06, stations[-1] - stations[0])
		while left + 1e-06 < right:
			mid = (left + right) / 2
			count = 0
			for (a, b) in zip(stations, stations[1:]):
				count += math.ceil((b - a) / mid) - 1
			if count > K:
				left = mid
			else:
				right = mid
		return right


class Solution:

	def findSmallestMaxDist(self, stations, K):
		lo = 0
		hi = stations[-1] - stations[0]
		eps = 1e-06

		def ispossible(mid):
			stationstoadd = 0
			for i in range(len(stations) - 1):
				stationstoadd += (stations[i + 1] - stations[i]) // mid
			if stationstoadd <= K:
				return True
			return False
		while hi - lo > eps:
			mid = (lo + hi) / 2
			if ispossible(mid):
				hi = mid
			else:
				lo = mid
		return hi


class Solution:

	def findSmallestMaxDist(self, stations, K):
		(low, high) = (0, stations[-1] - stations[0])

		def IsPossible(distance):
			stations_to_add = 0
			for i in range(len(stations) - 1):
				stations_to_add += math.floor((stations[i + 1] - stations[i]) / distance)
			return stations_to_add <= K
		while high - low > 1e-06:
			mid = low + (high - low) / 2.0
			if IsPossible(mid):
				high = mid
			else:
				low = mid
		return high


class Solution:

	def findSmallestMaxDist(self, stations, K):
		(low, high) = (0, stations[-1] - stations[0])

		def isValid(dis):
			add = 0
			for i in range(1, len(stations)):
				add += (stations[i] - stations[i - 1]) // dis
			return add <= K
		res = high
		while high - low > 1e-05:
			mid = (low + high) / 2
			if isValid(mid):
				high = mid
			else:
				low = mid
		return high


from math import floor

class Solution:

	def findSmallestMaxDist(self, stations, K):

		def isValid(d):
			new_stations = 0
			for i in range(1, len(stations)):
				new_stations += floor((stations[i] - stations[i - 1]) / d)
			return new_stations <= K
		start = 0
		end = stations[-1] - stations[0]
		while end - start > 1e-06:
			mid = (start + end) / 2
			if isValid(mid):
				end = mid
			else:
				start = mid
		return start + 1e-06


class Solution:

	def findSmallestMaxDist(self, stations, K):

		def isfeasible(D, arr, k):
			u = 0
			for i in range(len(arr) - 1):
				u += (arr[i + 1] - arr[i]) // D
			return u <= k
		h = stations[-1] - stations[0]
		l = 0
		while h - l > 1e-05:
			m = (l + h) / 2
			if isfeasible(m, stations, K):
				h = m
			else:
				l = m
		return h


from math import floor

class Solution:

	def addgas(self, arr, n, k, limit):
		added_gas = 0
		for i in range(n - 1):
			added_gas += floor((arr[i + 1] - arr[i]) / limit)
		return added_gas <= k

	def findSmallestMaxDist(self, stations, K):
		n = len(stations)
		low = 0
		high = stations[-1]
		while high - low > 1e-06:
			mid = (low + high) / 2
			if self.addgas(stations, n, K, mid):
				high = mid
			else:
				low = mid
		return high


class Solution:

	def findSmallestMaxDist(self, stations, k):
		max_distance = 0
		for i in range(len(stations) - 1):
			max_distance = max(max_distance, stations[i + 1] - stations[i])
		start = 0
		end = max_distance
		while end - start > 1e-06:
			mid = (start + end) / 2
			if self.check_distance(stations, k, mid) == True:
				end = mid
			else:
				start = mid
		return end

	def check_distance(self, stations, k, mid):
		count = 0
		for i in range(len(stations) - 1):
			count += (stations[i + 1] - stations[i]) // mid
		return count <= k


class Solution:

	def findSmallestMaxDist(self, stations, K):
		stations.sort()
		low = 0
		high = stations[-1] - stations[0]
		while high - low > 1e-05:
			mid = (low + high) / 2
			if self.is_possible(mid, stations, K):
				high = mid
			else:
				low = mid
		return round(high, 2)

	def is_possible(self, dist, stations, k):
		new_stations = 0
		for i in range(1, len(stations)):
			new_stations += (stations[i] - stations[i - 1]) // dist
		return new_stations <= k


import math

class Solution:

	def findSmallestMaxDist(self, stations, k):

		def possible(stations, dist, k):
			possibe_stations = 0
			for i in range(1, len(stations)):
				possibe_stations += math.floor((stations[i] - stations[i - 1]) / dist)
			return possibe_stations <= k
		l = 0
		h = stations[-1] - stations[0]
		while h - l > 1e-06:
			m = (l + h) / 2.0
			if possible(stations, m, k):
				h = m
			else:
				l = m
		return l + 1e-06


import math
from math import floor

class Solution:

	def findSmallestMaxDist(self, stations, K):

		def countStations(dist):
			count = 0
			for i in range(n - 1):
				count += floor((stations[i + 1] - stations[i]) / dist)
			return count <= K
		n = len(stations)
		l = 0
		r = 0
		for i in range(n - 1):
			r = max(r, stations[i + 1] - stations[i])
		while r - l > 1e-06:
			mid = l + (r - l) / 2.0
			if countStations(mid):
				r = mid
			else:
				l = mid
		return r


class Solution:

	def findSmallestMaxDist(self, stations, K):
		lo = 0
		hi = stations[-1] - stations[0]
		ans = hi

		def rec(val, K):
			ct = 0
			las = None
			n = len(stations)
			for i in range(1, n):
				ct += (stations[i] - stations[i - 1]) // val
			return ct <= K
		while hi - lo > 1e-05:
			mid = (lo + hi) / 2
			if rec(mid, K):
				ans = mid
				hi = mid
			else:
				lo = mid
		return ans


import math

class Solution:

	def isPossible(self, stations, distance, k):
		stations_to_add = 0
		for i in range(1, len(stations)):
			stations_to_add += (stations[i] - stations[i - 1]) // distance
		return stations_to_add <= k

	def findSmallestMaxDist(self, stations, k):
		(low, high) = (0, max(stations) - min(stations))
		while high - low > 1e-05:
			mid = low + (high - low) / 2.0
			if self.isPossible(stations, mid, k):
				high = mid
			else:
				low = mid
		return high


class Solution:

	def findSmallestMaxDist(self, stations, K):
		n = len(stations)
		(l, h) = (0, stations[-1] - stations[0])
		while h - l > 1e-05:
			mid = (l + h) / 2
			if self.possiblestations(stations, K, mid):
				h = mid
			else:
				l = mid
		return h

	def possiblestations(self, stations, k, maxdist):
		stat = 0
		for i in range(1, len(stations)):
			stat += (stations[i] - stations[i - 1]) // maxdist
		return stat <= K


class Solution:

	def findSmallestMaxDist(self, arr, K):
		i = 0
		j = arr[-1] - arr[0]
		while j - i > 1e-05:
			mid = (i + j) / 2
			AddS = 0
			for t in range(1, len(arr)):
				AddS += (arr[t] - arr[t - 1]) // mid
			if AddS <= K:
				j = mid
			else:
				i = mid
		return j


class Solution:

	def findSmallestMaxDist(self, stations, k):
		delt = l = 5e-06
		r = 10 ** 8
		while l < r:
			mid = (l + r) / 2
			cnt = 0
			for i in range(len(stations) - 1):
				diff = abs(stations[i + 1] - stations[i])
				cnt += int(diff / mid)
			if cnt <= k:
				ans = mid
				r = mid - delt
			else:
				l = mid + delt
		return ans


class Solution:

	def findSmallestMaxDist(self, arr, K):
		(start, end) = (0, arr[-1] - arr[0])
		while end - start > 1e-05:
			mid = (end + start) / 2
			if self.ispossible(arr, K, mid):
				end = mid
			else:
				start = mid
		return end

	def ispossible(self, arr, K, dist):
		count = 0
		for i in range(1, len(arr)):
			count += (arr[i] - arr[i - 1]) // dist
		return count <= K


import math

class Solution:

	def findSmallestMaxDist(self, stations, K):

		def feasible(m):
			st = 0
			for i in range(len(stations) - 1):
				st += math.floor((stations[i + 1] - stations[i]) / m)
			return st <= K
		(left, right) = (0, stations[-1] - stations[0])
		while right - left > 1e-06:
			mid = (left + right) / 2.0
			if feasible(mid):
				right = mid
			else:
				left = mid
		return right


class Solution:

	def findSmallestMaxDist(self, stations, K):

		def possible(mid, K):
			pairs = 0
			for i in range(1, len(stations)):
				diff = stations[i] - stations[i - 1]
				pairs += int(diff / mid)
			if pairs <= K:
				return True
			return False
		s = 0
		e = stations[-1] - stations[0]
		res = e
		while e - s > 1e-06:
			mid = s + (e - s) / 2
			if possible(mid, K):
				e = mid
				res = mid
			else:
				s = mid
		return res


class Solution:

	def findSmallestMaxDist(self, stations, K):
		n = len(stations)
		low = 0
		high = stations[n - 1] - stations[0]
		while high - low > 1e-06:
			mid = (low + high) / 2
			if self.canPlaceKStation(stations, n, mid, K) > K:
				low = mid
			else:
				high = mid
		return high

	def canPlaceKStation(self, stations, n, min_dis, K):
		count = 0
		for index in range(0, n - 1):
			count += (stations[index + 1] - stations[index]) // min_dis
			if count > K:
				break
		return count


class Solution:

	def findSmallestMaxDist(self, s, k):

		def check(m):
			c = 0
			for i in range(1, len(s)):
				d = s[i] - s[i - 1]
				if d <= m:
					continue
				else:
					c += d // m
			return c <= k
		n = len(s)
		(td, md) = (s[n - 1] - s[0], float('-inf'))
		(res, l, r) = (-1, 0, td)
		while r - l > 1e-06:
			m = l + (r - l) / 2
			if check(m):
				res = m
				r = m
			else:
				l = m
		return res


import math

class Solution:

	def check(self, stations, K, mid):
		count = 0
		for i in range(len(stations) - 1):
			count += math.floor((stations[i + 1] - stations[i]) / mid)
		return count <= K

	def findSmallestMaxDist(self, stations, K):
		start = 0
		end = stations[-1] - stations[0]
		while end - start > 1e-06:
			mid = start + (end - start) / 2.0
			if self.check(stations, K, mid):
				end = mid
			else:
				start = mid
		return end


class Solution:

	def canDivide(self, mid, target, nums):
		ways = 1
		s = 0
		for i in range(len(nums)):
			s += nums[i]
			if nums[i] > mid:
				return False
			if s > mid:
				ways += 1
				s = nums[i]
		return ways <= target

	def findSmallestMaxDist(self, stations, k):
		low = max(nums)
		high = sum(nums)
		ans = float('inf')
		while low <= high:
			mid = (low + high) // 2
			if self.canDivide(mid, m, nums):
				ans = min(ans, mid)
				high = mid - 1
			else:
				low = mid + 1
		return ans

class Solution:

	def findSmallestMaxDist(self, stations, k):

		def canAllocate(value):
			available = 0
			for itr in range(0, len(stations) - 1):
				available += math.ceil((stations[itr + 1] - stations[itr]) / value) - 1
			if available <= k:
				return True
			return False
		low = 0
		high = max(stations) - min(stations)
		while high - low >= 1e-05:
			mid = (low + high) / 2
			if canAllocate(mid):
				high = mid
			else:
				low = mid
		return round(high, 2)


class Solution:

	def findSmallestMaxDist(self, stations, k):

		def canAllocate(value):
			available = 0
			for itr in range(0, len(stations) - 1):
				available += math.ceil((stations[itr + 1] - stations[itr]) / value) - 1
			if available <= k:
				return True
			return False
		low = 0
		high = max(stations) - min(stations)
		while high - low >= 1e-05:
			mid = (low + high) / 2
			if canAllocate(mid):
				high = mid
			else:
				low = mid
		return round(high, 2)


class Solution:

	def findSmallestMaxDist(self, s, K):

		def isvalid(mid):
			k = 0
			for i in range(1, len(s)):
				k += (s[i] - s[i - 1]) // mid
			return k <= K
		(lo, hi) = (0, s[len(s) - 1] - s[0])
		while hi - lo > 1e-06:
			mid = lo + (hi - lo) / 2
			if isvalid(mid):
				hi = mid
			else:
				lo = mid
		return hi


import math

class Solution:

	def findSmallestMaxDist(self, stations, K):
		(l, r) = (0, stations[-1] - stations[0])

		def isPossible(mid):
			station = 0
			for i in range(len(stations) - 1):
				station += math.floor((stations[i + 1] - stations[i]) / mid)
			return station <= K
		while r - l > 1e-06:
			mid = l + (r - l) / 2.0
			if isPossible(mid):
				r = mid
			else:
				l = mid
		return r