Aggressive Cows Problem using Binary Search

Problem

---

Core Idea

You are not directly placing cows.

Instead, you are guessing the answer (minimum distance) and checking:

“Is it possible to place all cows with at least this distance?”

---

Goal

Find the maximum possible minimum distance between any two cows.

---

Why Binary Search?

• Minimum distance (L) = 0

• Maximum distance (R) = max(stall) - min(stall)

So the answer lies in a range → perfect for binary search.

---

Example

Stalls = [1, 2, 4, 8, 9]
Cows = 3

---

Step 1: Sort

[1, 2, 4, 8, 9]

Step 2: Apply Binary Search on distance

Range:

l = 0
r = 9 - 1 = 8

Search space:

0 1 2 3 4 5 6 7 8
l               r

Step 3: Try Mid Values

mid = (L + R)/2 =(0+8)/2 = 4

0 1 2 3 4 5 6 7 8
l       m       r

Try placing cows with minimum distance = 4

Stalls:  1   2   4   8   9

• Place 1st cow at 1

• 2-1 ≥ 4 → Distance Smaller than minimum distance 4. So, cannot place cow

• 4-1 ≥ 4 → Distance Smaller than minimum distance 4. So, cannot place cow

• 8-1 ≥ 4 → place 2nd cow at 8

• 9-8 ≥ 4 → Distance Smaller than minimum distance 4. So, cannot place cow

2 cows placed

Since we cannot place all 3 cows with a minimum distance of 4, it is impossible to place them with any larger distance like 5, 6, 7, or 8.

So:

r = mid - 1 = 3

---

mid = (L + R)/2 =(0+3)/2 = 2

0 1 2 3 4 5 6 7 8
l   m r           

Try placing cows with minimum distance = 2

Stalls:  1   2   4   8   9

• Place 1st cow at 1

• 2-1 ≥ 2 → Distance Smaller than minimum distance 2. So, cannot place cow

• 4-1 ≥ 2 place 2nd cow at 4

• 8-4 ≥ 2 → place 2nd cow at 8

3 cows placed

Since all 3 cows can be placed with a minimum distance of 2, we try to maximize the distance further by checking for a larger value.

So:

ans = 2
l = mid + 1 = 3

---

mid = (L + R)/2 = (3 + 3)/2 = 3

0 1 2 3 4 5 6 7 8
      l
      m
      r                  

Try placing cows with minimum distance = 3

Stalls:  1   2   4   8   9

• Place 1st cow at 1

• 2-1 ≥ 3 Distance Smaller than minimum distance 3. So cannot place cow

• 4-1 ≥ 3→ place 2nd cow at 4

• 8-4 ≥ 3 → place 2nd cow at 8

3 cows placed

So:

ans = 3
l = mid + 1 = 4
r = 3

Loop break

Final Answer: 3

So, The minimum distance between cows in this case is 3, which is the largest among all possible ways.

---

Code :

#include <bits/stdc++.h>
using namespace std;

#define int long long

bool possible(int arr[], int mid, int n, int cow){
    int cowCount = 1;
    int prev = arr[0];

    for(int i = 1; i < n; i++){
        if(arr[i] - prev >= mid){
            cowCount++;
            prev = arr[i];
        }
    }

    return cowCount >= cow;
}

signed main() {
    int stall, cow;
    cin >> stall >> cow;

    int arr[stall];
    for(int i = 0; i < stall; i++){
        cin >> arr[i];
    }

    // Step 1: Sort stalls
    sort(arr, arr + stall);

    int l = 0;
    int r = arr[stall - 1] - arr[0];
    int ans = -1;

    // Step 2: Binary Search
    while(l <= r){
        int mid = (l + r) / 2;

        if(possible(arr, mid, stall, cow)){
            ans = mid;       // store answer
            l = mid + 1;     // try for bigger distance
        } else {
            r = mid - 1;     // try smaller distance
        }
    }

    cout << ans << endl;
}

---

Complexity:

• Time Complexity: O(n log n + n log(max distance))

• Space Complexity: O(1)