# PROBLEM LINK:

PRACTICE

*Editorialist:* Yogesh Yogendra

# DIFFICULTY:

Medium

# PREREQUISITES:

Binary Search

# PROBLEM:

Yogesh has built a new hospital, with N(2<= N <= 100,000) beds. The beds are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).

Their are C(2<= C <=N) number of COVID infected persons. To prevent the further infections, you have to assign the beds to infected persons in such a way that the minimum distance between any two of them is as large as possible.

What is the largest minimum distance?

### Constraints

(2 <= N <= 100,000)

(0 <= xi <= 1,000,000,000)

(2 <= C <= N)

### Input

t – the number of test cases, then t test cases follows.

- Line 1: Two space-separated integers: N and C
- Line 2: N space seperated integers representing the bed locations i.e xi

### Output

For each test case output one integer: the largest minimum distance.

## Sample Testcase 1:

### Input

1

5 3

1 2 8 4 9

### Output:

3

# EXPLANATION:

This question was basically the variation of Aggressive Cow Problem of SPOJ.I have expained this question in a video, Link = https://youtu.be/Zwp6M5sl36Q , go and have a look.

# SOLUTION:

```
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define ps(x,y) fixed<<setprecision(y)<<x
#define mod 1000000007
#define w(x) int x; cin>>x; while(x--)
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
w(T)
{
int n,c;
cin>>n>>c;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int lb = 1;
int ub = 1e9;
int ans = 0;
while(lb<=ub){
int mid = (lb+ub)/2;
int cow = 1;
int prev = a[0];
for(int i=1;i<n;i++){
if(a[i]-prev>=mid){
cow++;
prev = a[i];
if(c==cow) break;
}
}
if(cow==c) {
ans = mid;
lb = mid + 1;
}
else ub = mid - 1;
}
cout<<ans<<endl;
}
return 0;
}
```