Searching: Aggressive Cows

Problem Statement:

You are given an array, which denotes the position of the stall.

You are given k cows, you need to assign stalls to k cows such that the minimum distance between any two cows is the max possible.

Example:

Input: arr = [4, 2, 3, 6, 1] k = 2

Output: 5

You can place one cow at shed 1 and one cow at shed 6. Then the minimum distance is 5.

Solution Explanation:

We will use binary search to solve the problem.

Sort the stalls.

Then apply binary search, low will be the smallest possible distance, high will be the largest possible distance.

Then pick a middle and then apply binary search to arrive at the solution.

Time Complexity: O(nlogn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <numeric>

using namespace std;


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; 

    int r = stalls[n-1]-stalls[0]; 

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

        if(solve(m,k,stalls))
        {
            ans = m;
            l = m+1;
        }
        else
        {
            r = m-1;
        }
    }
    return ans;
}

int main() 
{
    vector<int> stalls = {4, 2, 3, 6, 1};

    int cows = 3;
    
    cout << aggressiveCows(stalls, cows) << endl;
    return 0;
}

Output

2