2.3 Wolf Placement in the Forest 🐺
Zoya is tasked with placing a number of wild wolves into scattered cages in a dark forest. The cages are unevenly distributed, and she needs to place the wolves in such a way that the minimum distance between any two wolves is maximised. The forest is dangerous, and placing wolves too close to each other could lead to chaos.
Given n cages placed at specific positions in a forest (represented as an array of integers arr[]), and k wolves to be placed in these cages, find the maximum possible minimum distance betwe
en any two wolves when placed optimally.
Constraints
2≤n≤10^5
2≤k≤n
0≤arr[i]≤10^9
Input Format
The first line contains two integers n (the number of cages) and k (the number of wolves).
The second line contains n space-separated integers, representing the positions of the cages.
Output Format
Output a single integer, which is the maximum possible minimum distance between any two wolves.
Example 1
Input:
6 4
0 3 4 7 10 9
Output:
3
Explanation:
The maximum possible minimum distance between any two wolves is 3 when 4 wolves are placed at positions {0, 3, 7, 10}. The distances between wolves are 3, 4, and 3, respectively.
Log In to solve the Question