// Problem: EV Charging Station Placement
// A highway authority wants to install k electric vehicle charging stations across n pre-approved locations along a highway. The locations are given as an array of integers representing their positions (in km) on the highway.
// To avoid congestion, the authority wants to place the stations such that the minimum distance between any two stations is as large as possible.
// Return that maximum possible minimum distance.
// Example1 :
 
// locations = [1, 2, 4, 8, 9],  k = 3
// Output: 3
 
// Explanation: Place stations at positions 1, 4, and 9.
//              Gaps: (4-1)=3, (9-4)=5 → minimum gap is 3.
//              No other placement of 3 stations gives a minimum gap > 3.

// Example2 :
// Input: locations[] = [10, 1, 2, 7, 5], k = 3
// Output: 4
 
// Explanation: Sort the locations → [1, 2, 5, 7, 10].
//              Place stations at positions 1, 5, and 10.
//              Gaps: (5-1)=4, (10-5)=5 → minimum gap is 4.
//              No other placement of 3 stations yields a minimum gap greater than 4.

// 




/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	
	private static int maxDistance(int[] location, int k){
		Arrays.sort(location);
		int low = 0;
		int high = location[location.length-1];
		int answer = 0;
		while(low<=high){
			int mid = low + (high-low)/2;
			if(canPlace(location,k,mid)){
				answer = mid;
				low = mid+1;
			}else{
				high = mid-1;
			}
		}
		return answer;
	} 
	
	private static boolean canPlace(int[] location, int k, int mid){
		int stationPlaced = 1;
		int lastPosition = location[0];
		for(int i = 1; i < location.length; i++){
			if(location[i]-lastPosition >= mid){
				stationPlaced++;
				lastPosition = location[i];
			}
			if(stationPlaced>=k){
				return true;
			}
		}
		return false;
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		//[1, 2, 4, 8, 9],  k = 3
		int[] location = new int[]{10,1,2,7,5};
		int k = 3; 
		
		System.out.println(maxDistance(location,k));
	}
}