[C++] Aggressive Cows || Binary Search
Devesh Yadav
30336
Binary SearchCC++Career

Question

You are given an array 'arr' consisting of 'n' integers which denote the position of a stall.
You are also given an integer 'k' which denotes the number of aggressive cows.
You are given the task of assigning stalls to 'k' cows such that the minimum distance between any two of them is the maximum possible.
Return the maximum possible minimum distance.

  • Ex :
    n = 3
    k = 2
    arr = {1,2,3}
    answer = 2
    Explanation - The max possible min distance will be 2 when 2 cows are placed at positions {1,3}. Here distance between cows is 2.

// check if it is possible to arrange k cows with keeping atleast 'gap' distance between them
bool solve(int gap, int k, vector<int>&arr){
    int prev = arr[0];
    k--;
    for(int i = 1; i<arr.size(); ++i){
        if(arr[i]-prev>=gap){
            k--;
            prev = arr[i];
        }
        if(k==0){return true;}
    }
    return false;
}


int aggressiveCows(vector<int> &stalls, int k)
{
    sort(stalls.begin(),stalls.end());
    int n = stalls.size();

    int l = 1;  // min possible distance.. 0 is min possible logically if all cows placed at the same place.
                // So we initialize our ans = 0 since it is min possible
    int r = stalls[n-1]-stalls[0];   // this is max possible distance 

    int ans = 0;
    while(l<=r){
        int m = l+(r-l)/2;

        // check if it is possible to arrange k cows with keeping atleast 'm' distance between them
        if(solve(m,k,stalls)){
            ans = m;
            l = m+1;
        }
        else{
            r = m-1;
        }
    }
    return ans;
}

TC - O(nlogn)
SC - O(1)

Comments (4)