Aggressive_cows.java

/*

Given an integer array arr[], which denotes the positions of stalls. All the positions are distinct.
There are k aggressive cows.

Assign the cows to the stalls such that the minimum distance between any two cows is maximized.

Examples:

Input: arr[] = [1, 2, 4, 8, 9], k = 3
Output: 3
Explanation: The first cow can be placed at arr[0], the second at arr[2], and the third at arr[3]. 
The minimum distance between any two cows is 3 (between arr[0] and arr[2]), 
which is the maximum possible among all valid arrangements.

Input: arr[] = [10, 1, 2, 7, 5], k = 3
Output: 4
Explanation: The first cow can be placed at arr[0], the second at arr[1], and the third at arr[4]. 
In this arrangement, the minimum distance between any two cows is 4 (between arr[1] and arr[4]), 
which is the maximum possible among all valid arrangements.

Constraints:
2 ≤ arr.size() ≤ 106
0 ≤ arr[i] ≤ 108
2 ≤ k ≤ arr.size()

*/

import java.util.*;
class Aggressive_Cows {
    public int aggressiveCows(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);
        int low = 1;
        int high = arr[n-1] - arr[0];
        int res = 0;
        while(low<=high){
            int guess = (low+high)/2;
            if(cows(arr,k,guess) == true){
                res = guess;
                low = guess +1;
            }
            else{
                high = guess -1;
            }
        
        }
        return res;
        
    }
    public boolean cows (int [] arr , int k , int guess){
        int n = arr.length;
        int cow = 1;
        int pos = arr[0];
        boolean flag = false;
        for(int i = 1 ; i<n ; i++){
            int dist = arr[i]-pos;
            
            if(dist>=guess){
                cow ++;
                pos = arr[i];
            }
            else{
                continue;
            }
        }
        if(cow>= k){
            flag =  true;
        }
        else{
            flag = false;
        }
        return flag;
        
    }
}