485. Aggressive Cows (Maximum Minimum Distance)

Given positions of stalls along a line and a number of cows, place the cows in stalls so that the minimum distance between any two cows is as large as possible. Return that largest possible minimum distance. Input: '[stalls], cows'.

Input: '[stalls], cows'.

Output: Integer — the maximum minimum distance.

Examples

Input: [1,2,8,4,9], 3
Output: 3
Explanation: Place at 1,4,8 (or 1,4,9): min gap 3.

Input: [1,2,3,4,5], 5
Output: 1
Explanation: All stalls used; min gap 1.

Input: [1,5], 2
Output: 4
Explanation: Two stalls, distance 4.

Constraints

• 2<=cows<=n<=10^5
• 0<=position<=10^9

Asked by