# Aggressive Cows Problem using Binary Search

## Problem

![](https://cdn.hashnode.com/uploads/covers/624226a5db84f8c50fa5b247/a3ae3566-f774-4693-91f3-c844b0543faf.png align="left")

* * *

## 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

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

* * *

### Step 1: Sort

```plaintext
[1, 2, 4, 8, 9]
```

### Step 2: Apply Binary Search on distance

Range:

```plaintext
l = 0
r = 9 - 1 = 8
```

Search space:

```plaintext
0 1 2 3 4 5 6 7 8
l               r
```

### Step 3: Try Mid Values

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

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

Try placing cows with minimum distance = 4

```plaintext
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:

```plaintext
r = mid - 1 = 3
```

* * *

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

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

Try placing cows with minimum distance = 2

```plaintext
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:

```plaintext
ans = 2
l = mid + 1 = 3
```

* * *

**mid =** `(L + R)/2` **\=** `(3 + 3)/2 = 3`

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

Try placing cows with minimum distance = 3

```plaintext
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:

```plaintext
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 :

```js
#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)**