Java Programming

1. Maximum Minimum Distance for Goat Placement in Stalls

Background:

Farmer Berry has built a new linear barn with a number of stalls. Due to the aggressive behaviour of his goats when they are close to each other, he needs to find an optimal way to place the goats in these stalls to maximize the minimum distance between any two goats.

Problem Description:

You are given N stalls located along a straight line, each stall at a specific position xi. You are also given G goats. Your task is to place these goats in the stalls such that the minimum distance between any two goats is as large as possible.

Objective:

Determine the largest possible minimum distance between any two goats placed in the stalls.

Input Format:

• First Line: Two space-separated integers: N (number of stalls, 2 <= N <= 100,000) and G (number of goats, 2 <= G <= N).
• Next N lines: Each line contains an integer representing the stall location xi (0 <= xi <= 1,000,000,000).

Output:

• A single integer represents the largest minimum distance possible.

Example:

Input:

5 3
1
2
8
4
9

Output:

3