Commit-X- Question 4

Problem Statement

You are given an array arr of size n which denotes the position of stalls. You are also given an integer k which denotes the number of aggressive cows. The task is to assign stalls to k cows such that the minimum distance between any two of them is maximized. Find the maximum possible minimum distance.

Example Test Cases

Test Case 1

Input:

6   
6 7 9 11 13 15  
4

Output

2

Explanation:

We can place cow 1 at position 6, cow 2 at position 9, cow 3 at position 11 and cow 4 at position 15. So, the maximum possible minimum distance between two cows is 2.

Test Case 2

Input

5
1 2 8 4 9
3

Output

3

Explaination:

We can place cow 1 at position 1, cow 2 at position 4, cow 3 at position 8. So, the maximum possible minimum distance between two cows is 3.

Test Case 3

Input

5
10 1 2 7 5
2

Output

9