You are given an array consisting of n integers which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. You are given the task of assigning stalls to k cows such that the minimum distance between any two of them is the maximum possible.
The first line of input contains two space-separated integers n and k.
The second line contains n space-separated integers denoting the position of the stalls.
Example 1:
Input:
n=5 
k=3
stalls = [1 2 4 8 9]
Output:
3
Explanation:
The first cow can be placed at stalls[0], 
the second cow can be placed at stalls[2] and 
the third cow can be placed at stalls[3]. 
The minimum distance between cows, in this case, is 3, 
which also is the largest among all possible ways.
Example 2:
Input:
n=5 
k=3
stalls = [10 1 2 7 5]
Output:
4
Explanation:
The first cow can be placed at stalls[0],
the second cow can be placed at stalls[1] and
the third cow can be placed at stalls[4].
The minimum distance between cows, in this case, is 4,
which also is the largest among all possible ways.
Your Task:
Complete the function int solve(), which takes integer n, k, and a vector stalls with n integers as input and returns the largest possible minimum distance between cows.
Expected Time Complexity: O(n*log(10^9)).
Expected Auxiliary Space: O(1).
Constraints:
2 <= n <= 10^5
2 <= k <= n
0 <= stalls[i] <= 10^9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Starter code: #User function Template for python3



class Solution:

    def solve(self,n,k,stalls):

        pass

Solutions:
class Solution:

	def solve(self, n, k, stalls):
		if len(stalls) < k:
			return -1

		def cows(mid):
			count = 1
			latest_put_cow = 0
			for i in range(1, len(stalls)):
				if stalls[i] - stalls[latest_put_cow] >= mid:
					count += 1
					latest_put_cow = i
			return count
		stalls.sort()
		(left, right) = (1, stalls[-1] - stalls[0])
		ans = left
		while left <= right:
			mid = left + (right - left) // 2
			if cows(mid) >= k:
				ans = mid
				left = mid + 1
			else:
				right = mid - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()

		def check(mid):
			no = 1
			initial = stalls[0]
			for i in stalls:
				if no >= k:
					return True
				elif i - initial >= mid:
					no += 1
					initial = i
				else:
					continue
			else:
				if no >= k:
					return True
				return False
		left = 0
		right = stalls[-1] - stalls[0]
		while left <= right:
			mid = (left + right) // 2
			if check(mid):
				left = mid + 1
			else:
				right = mid - 1
		return right


class Solution:

	def can_assign_cows(self, stalls, k, dist):
		prev_cow_pos = stalls[0]
		n = 1
		for i in range(1, len(stalls)):
			if stalls[i] - prev_cow_pos >= dist:
				prev_cow_pos = stalls[i]
				n += 1
				if n == k:
					return True
		return False

	def solve(self, n, k, stalls):
		l = 0
		r = 10 ** 9
		max_dist = -float('inf')
		stalls.sort()
		while l <= r:
			dist = l + (r - l) // 2
			if self.can_assign_cows(stalls, k, dist):
				max_dist = max(max_dist, dist)
				l = dist + 1
			else:
				r = dist - 1
		return max_dist


class Solution:

	def solve(self, n, k, stalls):
		pass
		stalls.sort()

		def feasible(sep):
			prev = stalls[0]
			yes = 1
			for i in range(1, len(stalls)):
				if stalls[i] - prev >= sep:
					yes += 1
					prev = stalls[i]
			return yes >= k
		l = 1
		h = stalls[n - 1] - stalls[0]
		while l <= h:
			mid = (l + h) // 2
			if feasible(mid):
				l = mid + 1
			else:
				h = mid - 1
		return h


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()

		def placecows(diff):
			pos = stalls[0]
			cows = 1
			for i in range(1, len(stalls)):
				if stalls[i] - pos >= diff:
					cows += 1
					pos = stalls[i]
			if cows >= k:
				return True
			else:
				return False
		left = 1
		right = max(stalls)
		res = right
		while left <= right:
			mid = (left + right) // 2
			if placecows(mid):
				res = mid
				left = mid + 1
			else:
				right = mid - 1
		return res


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		ans = 0
		l = 1
		r = max(stalls) - min(stalls)
		while l <= r:
			mid = (l + r) // 2
			count = 1
			last = 0
			for i in range(1, len(stalls)):
				if abs(stalls[i] - stalls[last]) >= mid:
					count += 1
					last = i
			if count < k:
				r = mid - 1
			elif count >= k:
				ans = mid
				l = mid + 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		dist = stalls[-1] - stalls[0]
		lb = 1
		ub = dist

		def isCompatible(dist):
			lastcow = stalls[0]
			cows_placed = 1
			for i in range(1, n):
				if cows_placed == k:
					break
				if stalls[i] - lastcow >= dist:
					cows_placed += 1
					lastcow = stalls[i]
			if cows_placed == k:
				return True
			return False
		while lb <= ub:
			mid = lb + ub >> 1
			if isCompatible(mid):
				lb = mid + 1
			else:
				ub = mid - 1
		return ub


class Solution:

	def feasible(self, s, k, m):
		c = 1
		p = s[0]
		for i in range(1, len(s)):
			if s[i] - p >= m:
				c += 1
				p = s[i]
		return c >= k

	def solve(self, n, k, stalls):
		stalls.sort()
		l = 0
		r = stalls[n - 1] - stalls[0]
		ans = 0
		while l <= r:
			m = (l + r) // 2
			if self.feasible(stalls, k, m):
				ans = m
				l = m + 1
			else:
				r = m - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()

		def is_possible(distance):
			cows_placed = 1
			last_cow_position = stalls[0]
			for i in range(1, n):
				if stalls[i] - last_cow_position >= distance:
					cows_placed += 1
					last_cow_position = stalls[i]
				if cows_placed == k:
					return True
			return False
		lower_bound = 1
		upper_bound = stalls[n - 1] - stalls[0]
		max_distance = 0
		while lower_bound <= upper_bound:
			mid = lower_bound + (upper_bound - lower_bound) // 2
			if is_possible(mid):
				max_distance = mid
				lower_bound = mid + 1
			else:
				upper_bound = mid - 1
		return max_distance


class Solution:

	def solve(self, n, cowCount, stalls):
		stalls.sort()
		ans = 1
		l = 1
		h = stalls[-1] - stalls[0]
		while l <= h:
			mid = l + (h - l) // 2
			if self.isPossible(stalls, n, mid, cowCount):
				ans = mid
				l = mid + 1
			else:
				h = mid - 1
		return ans

	def isPossible(self, stalls, n, k, cowCount):
		cw = 1
		last_pos = 0
		for i in range(1, n):
			if stalls[i] - stalls[last_pos] >= k:
				cw += 1
				last_pos = i
		if cw >= cowCount:
			return True
		else:
			return False


class Solution:

	def solve(self, n, k, stalls):

		def possibleDistance(stalls, c, mid):
			last_pos = stalls[0]
			cow_placed = 1
			for i in range(1, len(stalls)):
				if stalls[i] - last_pos >= mid:
					cow_placed += 1
					last_pos = stalls[i]
				if cow_placed == c:
					return True
			return False
		l = 0
		h = max(stalls) - min(stalls)
		ans = 0
		stalls.sort()
		while l <= h:
			mid = l + (h - l) // 2
			if possibleDistance(stalls, k, mid):
				ans = mid
				l = mid + 1
			else:
				h = mid - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 0
		high = 10 ** 9
		mid = (low + high) // 2
		ans = -1
		while low <= high:
			if self.ispossible(stalls, n, k, mid):
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
			mid = (low + high) // 2
		return ans

	def ispossible(self, stalls, n, k, mid):
		cc = 1
		lp = stalls[0]
		for i in range(len(stalls)):
			if stalls[i] - lp >= mid:
				cc += 1
				if cc == k:
					return True
				lp = stalls[i]
		return False


class Solution:

	def solve(self, n, k, stalls):
		min_dis = float('-inf')
		stalls.sort()
		low = 1
		high = stalls[-1] - stalls[0]
		while low <= high:
			mid = low + (high - low) // 2
			if possible(stalls, k, mid):
				min_dis = max(mid, min_dis)
				low = mid + 1
			else:
				high = mid - 1
		return min_dis

def possible(stalls, k: int, d: int) -> bool:
	a = stalls[0]
	k -= 1
	if k == 0:
		return True
	for i in range(1, len(stalls)):
		if stalls[i] - a >= d:
			a = stalls[i]
			k -= 1
		if k == 0:
			return True
	return False


class Solution:

	def solve(self, n, k, stalls):

		def possible(a, cows, mid):
			cntCows = 1
			lastP = a[0]
			for i in range(1, len(a)):
				if a[i] - lastP >= mid:
					cntCows += 1
					lastP = a[i]
			if cntCows >= cows:
				return True
			else:
				return False

		def check(k, stalls):
			stalls.sort()
			low = 1
			high = stalls[-1] - stalls[0]
			while low <= high:
				mid = low + high >> 1
				if possible(stalls, k, mid):
					low = mid + 1
				else:
					high = mid - 1
			return high
		return check(k, stalls)


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		res = 0
		low = 1
		high = stalls[n - 1] - stalls[0]
		while low <= high:
			mid = low + high >> 1
			if self.can_place_cow(stalls, n, k, mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res

	def can_place_cow(self, stalls, n, k, mid):
		first = stalls[0]
		count = 1
		for i in range(1, n):
			if stalls[i] - first >= mid:
				count += 1
				first = stalls[i]
			if count == k:
				return True
		return False


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		(i, j) = (1, stalls[-1] - stalls[0])
		if k == 2:
			return j
		while i <= j:
			m = i + j >> 1
			c = 1
			curr = 0
			for x in range(1, n):
				dst = stalls[x] - stalls[curr]
				if dst >= m:
					c += 1
					curr = x
			if c >= k:
				i = m + 1
			else:
				j = m - 1
		return i - 1


class Solution:

	def correct(self, n, k, stalls, dis):
		c = 1
		cor = stalls[0]
		for i in range(1, n):
			if abs(stalls[i] - cor) >= dis:
				cor = stalls[i]
				c += 1
		return c >= k

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		res = low
		while low <= high:
			mid = low + high >> 1
			if self.correct(n, k, stalls, mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return high


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		l = 1
		r = stalls[n - 1] - stalls[0]
		ans = 0
		while l <= r:
			mid = (l + r) // 2
			cows = 1
			i = 0
			j = 1
			while i < n and j < n:
				if stalls[j] - stalls[i] >= mid:
					cows += 1
					i = j
				j += 1
			if cows >= k:
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans


def possible(k, stalls, dist, n):
	pre = stalls[0]
	k -= 1
	for i in range(1, n):
		if stalls[i] - pre >= dist:
			k -= 1
			pre = stalls[i]
	if k <= 0:
		return True
	return False

class Solution:

	def solve(self, n, k, stalls):
		l = 0
		stalls.sort()
		h = stalls[n - 1]
		res = 0
		while l <= h:
			mid = (l + h) // 2
			if possible(k, stalls, mid, n):
				res = mid
				l = mid + 1
			else:
				h = mid - 1
		return res


class Solution:

	def ispossible(self, arr, cows, gap):
		curr_stall = arr[0]
		cows -= 1
		for num in arr[1:]:
			if cows == 0:
				break
			if num - curr_stall >= gap:
				cows -= 1
				curr_stall = num
		return -1 if cows != 0 else gap

	def solve(self, n, k, stalls):
		stalls.sort()
		min_gap = 1
		max_gap = max(stalls)
		while min_gap <= max_gap:
			curr_gap = (min_gap + max_gap) // 2
			canbeplaced = self.ispossible(stalls, k, curr_gap)
			if canbeplaced != -1:
				candidate = curr_gap
				min_gap = curr_gap + 1
			else:
				max_gap = curr_gap - 1
		return candidate


class Solution(object):

	def solve(self, n, cows, stalls):

		def canPlaceAllCows(stalls, minDistance):
			(lastCowIndex, cowsPlaced) = (0, 1)
			for index in range(1, n):
				if stalls[index] - stalls[lastCowIndex] >= minDistance:
					lastCowIndex = index
					cowsPlaced += 1
					if cowsPlaced == cows:
						break
			return cowsPlaced == cows
		stalls.sort()
		(left, right) = (1, stalls[-1] - stalls[0])
		result = -1
		while left <= right:
			minDistance = (left + right) // 2
			if canPlaceAllCows(stalls, minDistance):
				result = minDistance
				left = minDistance + 1
			else:
				right = minDistance - 1
		return result


class Solution:

	def ispossible(self, stalls, mid, k):
		count = 1
		last = stalls[0]
		for ele in stalls[1:]:
			if ele - last >= mid:
				count += 1
				if count == k:
					return True
				last = ele
		return False

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[-1] - stalls[0]
		maxdist = 1
		while low <= high:
			mid = (low + high) // 2
			if self.ispossible(stalls, mid, k):
				maxdist = mid
				low = mid + 1
			else:
				high = mid - 1
		return maxdist


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()

		def helper(mid, k):
			last = stalls[0]
			k -= 1
			for i in range(1, n):
				curr = stalls[i]
				if curr - last >= mid:
					last = curr
					k -= 1
				if k == 0:
					return True
			return False
		l = 0
		r = stalls[n - 1] - stalls[0]
		ans = 0
		while l <= r:
			mid = l + (r - l) // 2
			if helper(mid, k):
				ans = max(ans, mid)
				l = mid + 1
			else:
				r = mid - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		left = 1
		right = stalls[n - 1] - stalls[0]
		ans = -1
		while left <= right:
			mid = (left + right) // 2
			cows = k - 1
			(i, j) = (0, 1)
			while j < n:
				if abs(stalls[j] - stalls[i]) < mid:
					j += 1
				else:
					cows -= 1
					i = j
					j += 1
			if cows > 0:
				right = mid - 1
			else:
				ans = max(mid, ans)
				left = mid + 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		lo = 1
		hi = stalls[-1] - stalls[0]
		ans = 0

		def possible(mid):
			cowat = stalls[0]
			cows = 1
			for i in range(1, len(stalls)):
				if stalls[i] - cowat >= mid:
					cowat = stalls[i]
					cows += 1
			if cows >= k:
				return True
			return False
		while lo <= hi:
			mid = lo + hi >> 1
			if possible(mid):
				if ans < mid:
					ans = mid
				lo = mid + 1
			else:
				hi = mid - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		l = 1
		r = stalls[-1] - stalls[0]
		while l <= r:
			mid = (l + r) // 2
			if self.possible(stalls, mid, k):
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans

	def possible(self, stalls, dis, k):
		prev = stalls[0]
		k -= 1
		for i in range(1, len(stalls)):
			if stalls[i] - prev >= dis:
				prev = stalls[i]
				k -= 1
			if k == 0:
				return True
		return False


class Solution:

	def solve(self, n, k, stalls):
		pass
		stalls.sort()
		(left, right, ans) = (0, stalls[-1] - stalls[0], -1)
		while left <= right:
			mid = left + (right - left) // 2
			(cows, last_pos) = (1, stalls[0])
			for i in range(1, n):
				if stalls[i] - last_pos >= mid:
					cows += 1
					last_pos = stalls[i]
			if cows >= k:
				ans = mid
				left = mid + 1
			else:
				right = mid - 1
		return ans


class Solution:

	def solve(self, n, cows, a):

		def isPossible(a, n, cows, mid):
			cntCows = 1
			lastPlacedCow = a[0]
			for i in range(1, n):
				if a[i] - lastPlacedCow >= mid:
					cntCows += 1
					lastPlacedCow = a[i]
				if cntCows >= cows:
					return True
			return False
		a.sort()
		low = 1
		high = a[n - 1] - a[0]
		while low <= high:
			mid = low + high >> 1
			if isPossible(a, n, cows, mid):
				low = mid + 1
			else:
				high = mid - 1
		return high


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		res = -1
		while low <= high:
			mid = low + high >> 1
			if self.can_place_cows(stalls, mid, n, k):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res

	def can_place_cows(self, stalls, barrier, n, cows):
		first_point = stalls[0]
		cows_placed = 1
		for i in range(n):
			if stalls[i] - first_point >= barrier:
				cows_placed += 1
				first_point = stalls[i]
			if cows_placed == cows:
				return True
		return False


class Solution:

	def allocation(self, stalls, mid, k):
		count = 1
		start = 0
		for i in range(len(stalls)):
			if stalls[i] - stalls[start] >= mid:
				count += 1
				start = i
		if count < k:
			return False
		return True

	def solve(self, n, k, stalls):
		start = 1
		end = max(stalls) - min(stalls)
		stalls.sort()
		res = -1
		while start <= end:
			mid = start + (end - start) // 2
			if self.allocation(stalls, mid, k):
				res = mid
				start = mid + 1
			else:
				end = mid - 1
		return res


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()

		def can(dist_bw_cows):
			bef = 0
			cnt = 1
			for i in range(1, n):
				if stalls[i] - stalls[bef] >= dist_bw_cows:
					bef = i
					cnt += 1
					if cnt >= k:
						return True
			return False
		(L, R) = (1, 10 ** 9)
		ans = None
		while L <= R:
			M = L + (R - L) // 2
			if can(M):
				ans = M
				L = M + 1
			else:
				R = M - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		res = -1
		stalls.sort()
		s = 1
		e = stalls[n - 1] - stalls[0]

		def isValid(arr, n, k, mid):
			c = 1
			p = 0
			cors = arr[0]
			for i in range(1, n):
				p = arr[i] - cors
				if p >= mid:
					c += 1
					cors = arr[i]
				if c == k:
					return True
			return False
		while s <= e:
			mid = s + (e - s) // 2
			if isValid(stalls, n, k, mid):
				res = mid
				s = mid + 1
			else:
				e = mid - 1
		return res


class Solution:

	def solve(self, n, k, stalls):

		def isPossible(barrier, stalls, n, k):
			num_cows = 0
			pichhla_guy_dist = None
			for i in range(n):
				if i == 0 or stalls[i] - pichhla_guy_dist >= barrier:
					num_cows += 1
					pichhla_guy_dist = stalls[i]
				if num_cows == k:
					return True
			return False
		stalls.sort()
		low = 0
		ans = -1
		high = stalls[n - 1] - stalls[0]
		while low <= high:
			mid = (high + low) // 2
			can = isPossible(mid, stalls, n, k)
			if can:
				low = mid + 1
				ans = mid
			else:
				high = mid - 1
		return ans


class Solution:

	def isPossible(self, dis, stalls, k):
		cnt = 1
		prev = stalls[0]
		for i in range(1, len(stalls)):
			if stalls[i] - prev >= dis:
				cnt += 1
				prev = stalls[i]
		if cnt >= k:
			return True
		return False

	def solve(self, n, k, stalls):
		stalls.sort()
		(low, high) = (1, stalls[-1] - stalls[0])
		while low <= high:
			mid = (low + high) // 2
			if self.isPossible(mid, stalls, k):
				low = mid + 1
			else:
				high = mid - 1
		return high


class Solution:

	def solve(self, n, k, stalls):

		def cowPass(dist):
			coOrd = stalls[0]
			count = 1
			for i in range(1, n):
				if stalls[i] - coOrd >= dist:
					count += 1
					coOrd = stalls[i]
				if count == k:
					return True
			return False
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		while low <= high:
			mid = low + (high - low) // 2
			if cowPass(mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()

		def fun(stalls, d, n, k):
			ans = 1
			prev = stalls[0]
			for i in range(1, n):
				if stalls[i] - prev >= d:
					ans += 1
					prev = stalls[i]
			return ans >= k
		l = 1
		h = max(stalls) + 1
		curr_ans = -1
		while l <= h:
			mid = (l + h) // 2
			temp = fun(stalls, mid, n, k)
			if temp:
				curr_ans = mid
				l = mid + 1
			else:
				h = mid - 1
		return curr_ans


class Solution:

	def solve(self, n, k, stalls):

		def isPossible(stalls, n, cows, minDist):
			cntCows = 1
			lastPlacedCow = stalls[0]
			for i in range(1, n):
				if stalls[i] - lastPlacedCow >= minDist:
					cntCows += 1
					lastPlacedCow = stalls[i]
			if cntCows >= cows:
				return True
			return False
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		while low <= high:
			mid = low + high >> 1
			if isPossible(stalls, n, k, mid):
				low = mid + 1
			else:
				high = mid - 1
		return high
		pass


class Solution:

	def canPlaceCows(self, arr, n, cows, dist):
		cord = arr[0]
		count = 1
		for i in range(1, n):
			if arr[i] - cord >= dist:
				count += 1
				cord = arr[i]
			if count == cows:
				return True

	def solve(self, n, k, arr):
		min_diff = 1
		res = 1
		size = len(arr)
		arr.sort()
		low = 1
		high = arr[n - 1] - arr[0]
		while low <= high:
			mid = (low + high) // 2
			if self.canPlaceCows(arr, n, k, mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res


def can_place_cows(stalls, n, k, distance):
	pos = stalls[0]
	cnt = 1
	for i in range(1, n):
		if stalls[i] - pos >= distance:
			pos = stalls[i]
			cnt += 1
		if cnt == k:
			return True
	return False

class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		high = stalls[n - 1] - stalls[0]
		low = 1
		res = 0
		while low <= high:
			mid = (low + high) // 2
			if can_place_cows(stalls, n, k, mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res


class Solution:

	def count(self, stalls, mid, n):
		prev = stalls[0]
		temp = 1
		for i in range(n):
			if stalls[i] - prev >= mid:
				temp += 1
				prev = stalls[i]
		return temp

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			temp = self.count(stalls, mid, n)
			if temp < k:
				high = mid - 1
			else:
				low = mid + 1
				ans = mid
		return ans


class Solution:

	def solve(self, N, k, stalls):
		stalls.sort()
		low = 0
		high = max(stalls) - min(stalls)
		res = -1
		while low <= high:
			mid = (low + high) // 2
			if self.allocation_ispossible(mid, stalls, k, N):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res

	def allocation_ispossible(self, mid, stalls, k, N):
		cow_count = 1
		last_pos = stalls[0]
		for i in range(N):
			if stalls[i] - last_pos >= mid:
				cow_count += 1
				if cow_count == k:
					return True
				last_pos = stalls[i]
		return False


class Solution:

	def canplacecows(self, n, k, v, mid):
		count = 1
		cord = v[0]
		for i in range(1, n):
			if v[i] - cord >= mid:
				count += 1
				cord = v[i]
			if count == k:
				return True
		return False

	def solve(self, n, k, v):
		res = -1
		v.sort()
		l = 1
		h = v[n - 1] - v[0]
		while l <= h:
			mid = (l + h) // 2
			if self.canplacecows(n, k, v, mid):
				res = mid
				l = mid + 1
			else:
				h = mid - 1
		return res


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		while low <= high:
			mid = (low + high) // 2
			if self.is_possible(stalls, mid, k):
				low = mid + 1
			else:
				high = mid - 1
		return high

	def is_possible(self, stalls, dis, cows):
		cntCows = 1
		lastPlacedCow = stalls[0]
		for i in range(1, len(stalls)):
			if stalls[i] - lastPlacedCow >= dis:
				cntCows += 1
				lastPlacedCow = stalls[i]
		if cntCows >= cows:
			return True
		return False


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		if k > n:
			return -1
		(low, high) = (0, stalls[-1] - stalls[0])
		res = 1

		def canPlace(val):
			count = 1
			cow = stalls[0]
			for i in range(1, n):
				if stalls[i] - cow >= val:
					count += 1
					cow = stalls[i]
				if count >= k:
					return True
			return False
		while low <= high:
			mid = (low + high) // 2
			if canPlace(mid):
				res = max(res, mid)
				low = mid + 1
			else:
				high = mid - 1
		return res


class Solution:

	def isPlace(stalls, cows, dist):
		coord = stalls[0]
		cnt = 1
		for i in range(1, len(stalls)):
			if stalls[i] - coord >= dist:
				cnt += 1
				coord = stalls[i]
		if cnt >= cows:
			return True
		else:
			return False

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[-1] - stalls[0]
		res = []
		while low <= high:
			mid = (low + high) // 2
			if Solution.isPlace(stalls, k, mid) == 1:
				low = mid + 1
				res.append(mid)
			else:
				high = mid - 1
		if res:
			return max(res)
		return -1


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()

		def possible(val):
			cnt = 1
			lstcow = stalls[0]
			for p in range(1, n):
				if stalls[p] - lstcow >= val:
					cnt += 1
					lstcow = stalls[p]
			if cnt >= k:
				return True
			else:
				return False
		l = 1
		r = max(stalls)
		res = -1
		while l <= r:
			mid = l + (r - l) // 2
			if possible(mid):
				res = mid
				l = mid + 1
			else:
				r = mid - 1
		return res


class Solution:

	def solve(self, n, k, stalls):
		if k > n:
			return -1
		stalls.sort()
		start = 1
		end = stalls[n - 1] - stalls[0]
		res = -1
		while start <= end:
			mid = start + (end - start) // 2
			if self.isvalid(stalls, n, k, mid):
				res = mid
				start = mid + 1
			else:
				end = mid - 1
		return res

	def isvalid(self, stalls, n, k, mx):
		cow = 1
		coord = stalls[0]
		for i in range(n):
			if stalls[i] - coord >= mx:
				cow += 1
				coord = stalls[i]
			if cow == k:
				return True
		return False


def iv(k, st, mid):
	c = 1
	pr = st[0]
	for i in range(1, len(st)):
		if st[i] - pr >= mid:
			c += 1
			pr = st[i]
	if c >= k:
		return True
	return False

class Solution:

	def solve(self, n, k, st):
		st.sort()
		e = st[-1] - st[0]
		b = 0
		while b < e:
			mid = (e + b) // 2
			if iv(k, st, mid):
				an = mid
				b = mid + 1
			else:
				e = mid
		return an


class Solution:

	def solve(self, n, k, stalls):

		def isPossible(stalls, n, cows, minDist):
			count = 1
			lastPlacedCow = stalls[0]
			for i in range(1, n):
				if stalls[i] - lastPlacedCow >= minDist:
					count += 1
					lastPlacedCow = stalls[i]
			if count >= cows:
				return 1
			return 0
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		while low <= high:
			mid = (low + high) // 2
			if isPossible(stalls, n, k, mid):
				low = mid + 1
			else:
				high = mid - 1
		return high


class Solution:

	def isPossible(self, n, k, stalls, mid):
		cowcount = 1
		position = stalls[0]
		for i in range(1, len(stalls)):
			if stalls[i] - position >= mid:
				cowcount += 1
				if cowcount == k:
					return True
				position = stalls[i]
		return False

	def solve(self, n, k, stalls):
		stalls.sort()
		start = 0
		end = stalls[n - 1]
		mid = start + (end - start) // 2
		ans = -1
		while start <= end:
			if self.isPossible(n, k, stalls, mid):
				ans = mid
				start = mid + 1
			else:
				end = mid - 1
			mid = start + (end - start) // 2
		return ans


class Solution:

	def AllocateCows(self, arr, count_cows, gap_limit):
		count_cows -= 1
		position = arr[0]
		for i in range(1, len(arr)):
			if arr[i] - position >= gap_limit:
				count_cows -= 1
				position = arr[i]
				if count_cows == 0:
					return True
		else:
			return False

	def solve(self, n, k, stalls):
		if k > len(stalls):
			return -1
		feasible_ans = -1
		stalls.sort()
		l = 1
		h = stalls[-1] - stalls[0]
		while l <= h:
			mid = l + (h - l) // 2
			if self.AllocateCows(stalls, k, mid):
				feasible_ans = mid
				l = mid + 1
			else:
				h = mid - 1
		return feasible_ans


class Solution:

	def solve(self, n, k, stalls):

		def isPossible(n, k, stalls, maxi):
			(cow, cur) = (1, stalls[0])
			for i in range(n):
				if stalls[i] - cur >= maxi:
					cow += 1
					if cow == k:
						return True
					cur = stalls[i]
			return False
		ans = -1
		(l, r) = (0, max(stalls))
		stalls.sort()
		while l <= r:
			mid = l + (r - l) // 2
			if isPossible(n, k, stalls, mid):
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0] + 1

		def isTrue(mid):
			left = 0
			total = 1
			for i in range(1, n):
				if stalls[i] - stalls[left] >= mid:
					left = i
					total += 1
					if total == k:
						return True
			return False
		res = 1
		while low <= high:
			mid = (low + high) // 2
			if isTrue(mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		start = 0
		end = 10 ** 9
		ans = -1
		while start <= end:
			middle = start + (end - start) // 2
			prev = stalls[0]
			c = 1
			for i in stalls:
				if i - prev >= middle:
					prev = i
					c += 1
			if c >= k:
				ans = middle
				start = middle + 1
			else:
				end = middle - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):

		def ispossible(mid):
			cooordinate = stalls[0]
			cnt = 1
			for i in range(1, n):
				if stalls[i] - cooordinate >= mid:
					cnt += 1
					cooordinate = stalls[i]
				if cnt == k:
					return True
			return False
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		res = 0
		while low <= high:
			mid = (low + high) // 2
			if ispossible(mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res


import sys

class Solution:

	def solve(self, n, k, stalls):
		l = 1
		stalls.sort()
		r = stalls[-1] - stalls[0]
		mindiff = -sys.maxsize
		while l <= r:
			mid = (l + r) // 2
			last = -sys.maxsize
			diff = sys.maxsize
			c = 0
			for i in range(n):
				if stalls[i] - last >= mid:
					diff = min(diff, stalls[i] - last)
					last = stalls[i]
					c += 1
				if c == k:
					break
			if c == k:
				mindiff = max(mindiff, diff)
				l = mid + 1
			else:
				r = mid - 1
		return mindiff


class Solution:

	def valid(self, n, k, stalls, mid):
		pos = stalls[0]
		cc = 1
		for i in range(1, n):
			if stalls[i] - pos >= mid:
				cc += 1
				pos = stalls[i]
			if cc == k:
				return True
		return False

	def solve(self, n, k, stalls):
		stalls = sorted(stalls)
		mindist = stalls[0]
		maxdist = stalls[n - 1]
		low = 0
		high = maxdist - mindist
		ans = 1
		while low <= high:
			mid = (low + high) // 2
			if self.valid(n, k, stalls, mid):
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):

		def isPossible(n, k, stalls, max_dist):
			(cur_dist, count) = (stalls[0], 1)
			for i in range(n):
				if stalls[i] - cur_dist >= max_dist:
					count += 1
					if count == k:
						return True
					cur_dist = stalls[i]
			return False
		ans = -1
		(l, r) = (0, max(stalls))
		stalls.sort()
		while l <= r:
			mid = l + (r - l) // 2
			if isPossible(n, k, stalls, mid):
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans


class Solution:

	def num_cows(self, arr, min_dist):
		cows = 1
		curr = arr[0]
		for i in range(1, len(arr)):
			if arr[i] - curr >= min_dist:
				cows += 1
				curr = arr[i]
		return cows

	def solve(self, n, k, stalls):
		start = 1
		end = max(stalls) - min(stalls)
		ans = 1
		stalls.sort()
		while start <= end:
			mid = (start + end) // 2
			curr_cows = self.num_cows(stalls, mid)
			if curr_cows < k:
				end = mid - 1
			else:
				ans = max(ans, mid)
				start = mid + 1
		return ans


class Solution:

	def canPlaceCows(self, n, k, stalls, dist):
		curr = stalls[0]
		count = 1
		for i in range(1, n):
			if stalls[i] - curr >= dist:
				curr = stalls[i]
				count += 1
			if count == k:
				return True
		return False

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		res = 1
		while low <= high:
			mid = low + (high - low) // 2
			if self.canPlaceCows(n, k, stalls, mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res
		pass


from typing import List

class Solution:

	def isPossible(self, stalls: List[int], min_dist: int, cows: int) -> bool:
		last_cow = float('-inf')
		cows_placed = 0
		for stall in stalls:
			if stall - last_cow < min_dist:
				continue
			else:
				last_cow = stall
				cows_placed += 1
		return cows_placed >= cows

	def solve(self, n, k, stalls):
		stalls.sort()
		result = None
		low = 1
		high = stalls[-1]
		while low <= high:
			mid = (low + high) // 2
			if self.isPossible(stalls, mid, k):
				result = mid
				low = mid + 1
			else:
				high = mid - 1
		return result


class Solution:

	def solve(self, n, k, arr):
		arr.sort()
		low = 0
		high = arr[n - 1] - arr[0]
		res = []
		while low <= high:
			mid = low + (high - low) // 2
			if self.cow_Place(arr, n, k, mid):
				res.append(mid)
				low = mid + 1
			else:
				high = mid - 1
		return max(res)

	def cow_Place(self, arr, n, k, mid):
		i = 0
		j = 1
		count = 1
		while j < n:
			if arr[j] - arr[i] >= mid:
				count += 1
				i = j
				if count == k:
					return True
			j += 1
		return False


class Solution:

	def solve(self, n, k, stalls):
		s = 0
		e = max(stalls)
		ans = 0
		mid = s + (e - s) // 2
		stalls.sort()

		def isPossible(stalls, k, mid):
			cowCount = 1
			lastPos = stalls[0]
			for i in range(len(stalls)):
				if stalls[i] - lastPos >= mid:
					cowCount += 1
					if cowCount == k:
						return True
					lastPos = stalls[i]
			return False
		while s <= e:
			if isPossible(stalls, k, mid):
				ans = mid
				s = mid + 1
			else:
				e = mid - 1
			mid = s + (e - s) // 2
		return ans


class Solution:

	def canAssignCows(self, cows, stalls, mid):
		j = 1
		lastStall = 0
		for i in range(1, cows):
			while j < len(stalls):
				distanceCovered = stalls[j] - stalls[lastStall]
				if distanceCovered >= mid:
					lastStall = j
					break
				j += 1
			if i >= cows:
				return True
			elif j >= len(stalls) and i < cows:
				return False
		return True

	def aggressiveCows(self, cows, stalls):
		start = 1
		stalls.sort()
		end = stalls[-1] - stalls[0]
		ans = end
		while start <= end:
			mid = start + (end - start) // 2
			if self.canAssignCows(cows, stalls, mid):
				ans = mid
				start = mid + 1
			else:
				end = mid - 1
		return ans

	def solve(self, n, k, stalls):
		return self.aggressiveCows(k, stalls)


class Solution:

	def bn(self, k, mid, arr):
		pos = arr[0]
		cow = 1
		for i in arr:
			if i - pos >= mid:
				cow += 1
				if cow == k:
					return True
				pos = i
		return False

	def solve(self, n, k, stalls):
		stalls.sort()
		s = 0
		e = max(stalls)
		mid = (s + e) // 2
		ans = -1
		while s <= e:
			if self.bn(k, mid, stalls):
				ans = mid
				s = mid + 1
			else:
				e = mid - 1
			mid = (s + e) // 2
		return ans


class Solution:

	def check(self, mid, stalls, k):
		temp = stalls[0]
		count = 1
		for i in stalls:
			if i - temp >= mid:
				temp = i
				count += 1
			if count == k:
				return 1
		return 0

	def solve(self, n, k, stalls):
		stalls.sort()
		ans = 1
		min_diff = 1
		max_diff = stalls[-1] - stalls[0]
		while min_diff <= max_diff:
			mid = (min_diff + max_diff) // 2
			if self.check(mid, stalls, k):
				min_diff = mid + 1
				ans = max(ans, mid)
			else:
				max_diff = mid - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()

		def isok(stalls, n, k, dist):
			c = 1
			coord = stalls[0]
			for i in range(1, n):
				if stalls[i] - coord >= dist:
					c += 1
					coord = stalls[i]
				if c == k:
					return True
			return False
		low = 1
		high = stalls[n - 1] - stalls[0]
		while low <= high:
			mid = low + high >> 1
			if isok(stalls, n, k, mid):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res


class Solution:

	def solve(self, n, k, stalls):

		def cows(arr, c, n, dis):
			num1 = arr[0]
			s = 1
			for i in range(n):
				if arr[i] - num1 >= dis:
					s += 1
					num1 = arr[i]
				if s == c:
					return True
			return False
		stalls.sort()
		l = 0
		r = stalls[n - 1] - stalls[0]
		res = 0
		while l <= r:
			mid = (l + r) // 2
			if cows(stalls, k, n, mid):
				res = mid
				l = mid + 1
			else:
				r = mid - 1
		return res


class Solution:

	def solve(self, n, k, arr):
		arr.sort()
		low = 0
		high = arr[n - 1] - arr[0]
		res = []
		while low <= high:
			mid = low + high >> 1
			if self.cow_Place(arr, n, k, mid):
				res.append(mid)
				low = mid + 1
			else:
				high = mid - 1
		return max(res)

	def cow_Place(self, arr, n, k, mid):
		coor = arr[0]
		count = 1
		for i in range(1, n):
			if arr[i] - coor >= mid:
				count += 1
				coor = arr[i]
			if count == k:
				return True
		return False


class Solution:

	def isPossible(self, stalls, n, k, mid):
		cows = 1
		last = stalls[0]
		for i in range(n):
			if stalls[i] - last >= mid:
				cows += 1
				last = stalls[i]
				if cows == k:
					return True
		return False

	def solve(self, n, k, stalls):
		stalls.sort()
		s = 0
		ans = -1
		maxi = -1
		for i in range(n):
			maxi = max(maxi, stalls[i])
		e = maxi
		mid = s + (e - s) // 2
		while s <= e:
			if self.isPossible(stalls, n, k, mid):
				ans = mid
				s = mid + 1
			else:
				e = mid - 1
			mid = s + (e - s) // 2
		return ans


class Solution:

	def solve(self, n, k, nums):
		pass
		nums.sort()
		low = 1
		high = nums[-1] - nums[0]

		def canPlace(ch):
			cnt = 1
			pos = nums[0]
			for i in nums:
				if i - pos >= ch:
					pos = i
					cnt += 1
				if cnt == k:
					return True
			return False
		while low <= high:
			mid = low + (high - low) // 2
			if canPlace(mid) == True:
				low = mid + 1
			else:
				high = mid - 1
		return high


class Solution:

	def solve(self, n, k, stalls):
		(low, high) = (1, max(stalls) - min(stalls))
		res = 0
		stalls.sort()
		while low <= high:
			mid = (low + high) // 2
			if self.helper_func(mid, k, stalls):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res

	def helper_func(self, mid, k, stalls):
		curr_idx = 0
		count = 1
		for i in range(len(stalls)):
			if stalls[i] - stalls[curr_idx] >= mid:
				count += 1
				curr_idx = i
			if count == k:
				return True
		return False


class Solution:

	def solve(self, n, k, stalls):

		def valid(m, n, k, stalls):
			cnt = 1
			prev_cow = stalls[0]
			for i in range(1, len(stalls)):
				if stalls[i] >= prev_cow + m:
					cnt += 1
					prev_cow = stalls[i]
					if cnt == k:
						return True
			return False
		stalls.sort()
		l = 1
		h = max(stalls) - min(stalls)
		ans = -1
		while l <= h:
			m = l + (h - l) // 2
			if valid(m, n, k, stalls):
				ans = m
				l = m + 1
			else:
				h = m - 1
		return ans


class Solution:

	def solve(self, n, k, stalls):
		if k > n:
			return -1
		stalls.sort()
		st_min = 0
		st_max = -1
		for el in stalls:
			if st_max < el:
				st_max = el

		def possible(mid, stalls):
			cnt = 1
			prev = stalls[0]
			for i in range(1, len(stalls)):
				if stalls[i] - prev >= mid:
					cnt += 1
					prev = stalls[i]
				if cnt >= k:
					return True
			return False
		ans = -1
		while st_min <= st_max:
			mid = (st_min + st_max) // 2
			if possible(mid, stalls):
				ans = mid
				st_min = mid + 1
			else:
				st_max = mid - 1
		return ans


import bisect

class Solution:

	def solve(self, n, k, stalls):
		stalls = sorted(stalls)
		x = 1
		finn = []
		lower_bound = 0
		upper_bound = stalls[-1] + 1
		while True:
			start_index = 0
			flag = 0
			find = stalls[0]
			mid = (upper_bound + lower_bound) // 2
			cows_left = k - 1
			x = mid
			while True:
				range_start = start_index + 1
				to_find = find + x
				start_index = bisect.bisect_left(stalls, to_find)
				if start_index >= len(stalls) and cows_left > 0:
					flag = 1
					break
				cows_left = cows_left - 1
				find = stalls[start_index]
				if cows_left == 0:
					break
			if flag:
				upper_bound = mid - 1
			else:
				finn.append(mid)
				lower_bound = mid + 1
			if upper_bound < lower_bound:
				break
		return finn[-1]


class Solution:

	def solve(self, n, k, stalls):
		l = 0
		r = max(stalls) - min(stalls)
		stalls.sort()
		prev = -99999999999
		while l <= r:
			count = 0
			mid = (l + r) // 2
			for i in range(n):
				if abs(stalls[i] - prev) >= mid:
					count += 1
					prev = stalls[i]
			if count < k:
				r = mid - 1
			else:
				l = mid + 1
		return r


class Solution:

	def ispossible(self, stalls, mid, k):
		cow = 1
		lastcow = stalls[0]
		for i in range(1, len(stalls)):
			if stalls[i] >= lastcow + mid:
				cow += 1
				lastcow = stalls[i]
				if cow == k:
					return True
		return False

	def solve(self, n, k, stalls):
		stalls = sorted(stalls)
		left = 1
		right = max(stalls) - min(stalls)
		while left < right:
			mid = (left + right) // 2
			if self.ispossible(stalls, mid, k):
				left = mid + 1
			else:
				right = mid
		return left - 1


class Solution:

	def solve(self, n, k, stalls):

		def cows(a, n1, cow, md):
			c = 1
			lc = a[0]
			for i in range(1, n1):
				if a[i] - lc >= md:
					c += 1
					lc = a[i]
			if c >= cow:
				return True
			return False
		stalls.sort()
		l = 1
		h = stalls[n - 1] - stalls[0]
		while l <= h:
			m = l + h >> 1
			if cows(stalls, n, k, m):
				l = m + 1
			else:
				h = m - 1
		return h


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		l = []

		def find(arr, left, right, cows):
			if left <= right:
				mid = (left + right) // 2
				a = arr[0]
				k = cows - 1
				for i in range(1, n):
					b = arr[i]
					if b - a >= mid:
						k = k - 1
						a = b
				if k <= 0:
					l.append(mid)
					if left == right:
						return max(l)
					return find(arr, mid + 1, right, cows)
				else:
					return find(arr, left, mid - 1, cows)
			else:
				return max(l)
		return find(stalls, 0, max(stalls), k)


class Solution:

	def solve(self, n, k, stalls):
		stalls.sort()
		low = 1
		high = stalls[n - 1] - stalls[0]
		res = 0
		while low <= high:
			mid = low + (high - low) // 2
			if self.is_possible(mid, k, stalls):
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res

	def is_possible(self, distance, k, stalls):
		p = 1
		i = 0
		k -= 1
		while p < len(stalls):
			if abs(stalls[i] - stalls[p]) >= distance:
				k -= 1
				i = p
				if k == 0:
					return True
			p += 1
		return False