Skip to main content

Aggressive Cows Problem

Ayesha
EditReport

Problem - Statement​

  • You are given an array of N integers, representing the positions of stalls on a straight line. You also have C cows that are aggressive and need to be placed in these stalls. 🎯 The Goal
  • Place all C cows in the stalls such that the minimum distance between any two cows is as large as possible.

Video Explanation​

  • We use Binary Search because the search space for the answer is monotonic.
  • Eliminates Half the Work: Instead of checking every number, Binary Search cuts the range in half every time.

Code Implementation​

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//This function checks whether the arrangement is possible or not
bool isPossible(int stalls[], int cows, int stall_size, int min_distance) {
    int count = 1; // Place the first cow in the first stall
    int lastPos = stalls[0];

    for (int i = 1; i < stall_size; i++) {
        if (stalls[i] - lastPos >= min_distance) {
            count++;
            lastPos = stalls[i];
        }
        if (count >= cows) return true;
    }
    return false;
}

int AggressiveCows(int stalls[], int cows, int stall_size){
    sort(stalls, stalls + stall_size); //sort the array to perform Binary Search

    int start = 1, end = stalls[stall_size - 1] - stalls[0], ans = -1;

    //Binary Search Implementation
    while(start <= end) {
        int mid = start + (end - start) / 2;

        if(isPossible(stalls, cows, stall_size, mid)) {
            ans = mid;
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
    }

    return ans ;
}

int main(){
    int stalls[] = {1, 2, 8, 4, 9};
    int cows = 3;
    int stall_size = sizeof(stalls) / sizeof(stalls[0]);
    int min_distance = AggressiveCows(stalls, cows, stall_size); //stores the required answer
    cout << "Minimum Distance is: " << min_distance << endl;
    return 0;
}

Key Logic​

  • Sorting: The stalls array must be sorted so that the greedy placement of cows is possible.
  • Binary Search Range: The search range is between 1 (minimum possible distance) and stalls[n-1] - stalls[0] (maximum possible distance).
  • IsPossible Function: This function checks if it's possible to place c cows in the given stalls such that every pair of cows is at least minAllowedDist apart.
  • Time Complexity: The total complexity is roughly O(n∗log(Range))O(n * log(Range)), where n is the number of stalls and the Range is the difference between the maximum and minimum stall positions.
Track Your Progress

Done with this topic? Mark it as complete to track your progress.

💬 Discuss this page

Have a question or spot something confusing in "Aggressive Cows Problem"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.