# Aggressive Cows

## Introduction

In this article, we will discuss the problem of __Aggressive Cows.__ We will see both the naive approach and the optimized version of the solution. If you find this problem tricky, then do read till the end because here you will understand every step logically.

Let’s understand the problem statement in depth first to get a better understanding.

## Problem Statement

Farmer John has built a new long barn with **N** stalls. The stalls are located along a straight line at positions **x1,...,xN**.

His **C** (**2 <= C <= N**) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, John wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. **What is the largest minimum distance?**

__Please try to solve this problem on your own before moving on to further discussion here__

**Let’s jot down some points to reach the solution - **

**What do you mean by ‘minimum distance’ between the cows?**

Consider the minimum distance in an arrangement of cows is equal to **‘min_d’**. Then, in this arrangement, the distance between any two cows will always be greater than or equal to **min_d**.

**What can be the minimum distance between two cows?**

Since two cows can’t be placed in the same stall, the minimum possible distance can be 1.

**What can be the maximum distance between the cows?**

If **max(POS)** and** min(POS)** is the maximum and minimum of all the positions respectively in the POS array, then the maximum possible distance between the cows can be equal to **max(POS) - min(POS).**

**Note:**The above maximum and minimum distances might not be possible to arrange the cows. These values only determine the range in which the minimum distance will lie.- So we can say that the distance between two cows will always lie in the range
**[1, max(POS)-min(POS)]** - We need to find the minimum distance between the cows such that it is the largest minimum distance possible among all the possible arrangements of cows. Say the required distance is
**D**, then there can’t be any arrangement of cows such that the minimum distance between any two cows in this arrangement is greater than**D**.

Considering the above points, Let’s have a look at the naive approach.

## Naive/Brute Force Approach

- The range of the distance between any two cows is
**[1, max(POS)-min(POS)]** - For every distance ‘
**d’**in this range starting from**1**, check if it is possible to place the cows in stalls such that the minimum distance between any two cows is equal to**‘d’** - If distance
**‘d’**is possible, then update the largest minimum distance found so far.

Let us understand this approach by taking an example -

**Input:**

**Number of stalls** = 5 and **No. of Cows **= 3

Array positions is given as ** POS** = **[1,2,8,4,9]**

**Output:**

3

The possible arrangements of the three cows C1, C2 and C3, are as follows:

- Range of distances possible is -
**[1, (9-1)]**=**[1,8]** - So, in the column
**minimum distances,**the values run from**1 to 8**. - Up to
**minimum distance=3**, you can see that a proper arrangement exists. - After this, consider the rows one by one -
**Minimum distance=4**- To have a minimum distance of 4; first, we place the cows**C1 at 4**and**C2 at 8**. Then, to place the cow**C3**, we are left with positions**1, 2, and 9**. But if you place**C3**at 9 then the distance between**C2**and**C3**is 1, which is less than the minimum distance of 4. Then if**C3**is placed at 1, then the distance between**C3**and**C1**= 4-1 = 3 (again less than 4). For position 2 also the minimum distance we get is 4-2=2 (<4). So, the**red cross mark**represents that no such arrangement is possible in which the minimum distance between the cows is 4. And the entry**C3**in**red**in columns 1,2 and 9 represents that it is not a correct position for the third cow to be placed.- Similarly, for all the rows having a minimum distance > 3, no valid arrangement is possible.

### C++ Implementation

/* C++ code to find the largest minimum distance in the problem Aggressive Cows*/#include <bits/stdc++.h>using namespace std;/*function to check if it is possible to place the cows such that the minimum distancebetween the cows is currDist*/bool isPossible(int currDist, int POS[], int numStalls, int numCows){ int prevPos = POS[0]; //place the first cow at the first stall int numCowsPlaced = 1; for (int i = 1; i < numStalls; i++) { /*check if the distance is greater than or equal to currDist*/ if (POS[i] - prevPos >= currDist) { prevPos = POS[i]; //update prevPos numCowsPlaced++; /*increment number of cows placed by one*/ } /*If all cows have been placed with minimum distance = currDist*/ if (numCowsPlaced == numCows) { return true; } } /*not possible to place the cows with minimum distance = currDist*/ return false;}int largestMinimumDistance(int numStalls, int numCows, int POS[]){ /*sort the array POS*/ sort(POS, POS + numStalls); int maxDist = POS[numStalls - 1] - POS[0]; int minDist = 1; int largestMin = minDist; //initialize it with minDist for (int currDist = minDist; currDist <= maxDist; currDist++) { if (isPossible(currDist, POS, numStalls, numCows)) { largestMin = currDist; } } return largestMin;}int main(){ int numStalls = 5; int numCows = 3; int POS[numStalls] = {4, 2, 1, 3, 6}; cout << "The largest minimum distance possible is: " << largestMinimumDistance(numStalls, numCows, POS) << endl;} |

**Output**

The largest minimum distance possible is: 2 |

The three cows can be placed at positions {1,3, 6} to get the largest minimum distances.

The other distances possible are -

**{1,2,3} → Minimum distance = 1****{1,3,4} → Minimum distance = 1****{1,3,6} → Minimum distance = 2****{1,4,6} → Minimum distance = 2****Further, if you try to place the cows such that the minimum distance is greater than 2, you will find that no such arrangement can be possible. Hence, the largest minimum distance is 2.**

### Time Complexity - O(n^2)

Two loops are being used in the solution. The outer loop runs from minDist to maxDist, and in each iteration, we call the function isPossible, whose time complexity is **O(n)**. So, the total time complexity is **O(n^2)**.

### Space Complexity - O(log(N))

where ‘N’ is the number of elements in the given array.

The array, when sorted, will take **log(N)** space so that the overall space complexity will be **O(log(N))**.

**Can we optimize further? **

Yes, see the next section.

## Binary Search Approach

### Key Observations

- If for a minimum distance ‘d’ it is possible to place all the cows; then it will also be possible to place the cows with a minimum distance < ‘d’.
- If it is not possible to place the cows with a minimum distance of ‘d’, then for every distance > ‘d’ also there won’t be any valid arrangement.
- Thus, the problem satisfies the monotonicity condition necessary for binary search.

### Algorithm

- The range of the distance between any two cows is [1, max(POS)-min(POS)]
- Initialize low=1 and high = max(POS)-min(POS)
- Find mid = (low+high)/2.
- Check if it is possible to place the cows such that the minimum distance is equal to mid.
- If yes, then to get a larger value of minimum distance, update low to mid+1. Because there is no point in checking for distances less than mid as it will be possible to arrange the cows with those minimum distances. But since we want the largest minimum distance, we check for the distances > mid.
- If it is not possible to arrange the cows with a minimum distance equal to mid, then for every distance > mid also, it won’t be possible. So, update high to mid-1.

- Repeat the above steps until low<=high.

Let’s look at the C++ Implementation below.

### C++ Implementation

/* C++ code to find the largest minimum distance in the problem Aggressive Cows*/#include <bits/stdc++.h>using namespace std;/*function to check if it is possible to place the cows such that the minimum distance between the cows is currDist*/bool isPossible(int currDist, int POS[], int numStalls, int numCows){ int prevPos = POS[0]; //place the first cow at the first stall int numCowsPlaced = 1; for (int i = 1; i < numStalls; i++) { /*check if the distance is greater than or equal to currDist*/ if (POS[i] - prevPos >= currDist) { prevPos = POS[i]; //update prevPos numCowsPlaced++; //increment number of cows placed by one } /*If all cows have been placed with minimum distance = currDist*/ if (numCowsPlaced == numCows) { return true; } } /*not possible to place the cows with minimum distance = currDist*/ return false;}int largestMinimumDistance(int numStalls, int numCows, int POS[]){ /*sort the array POS*/ sort(POS, POS + numStalls); int high = POS[numStalls - 1] - POS[0]; int low = 1; int largestMin = low; //initialize it with minDist while (low <= high) { int mid = low + (high - low) / 2; if (isPossible(mid, POS, numStalls, numCows)) { largestMin = mid; low = mid + 1; } else { high = mid - 1; } } return largestMin;}int main(){ int numStalls = 5; int numCows = 3; int POS[numStalls] = {4, 2, 1, 3, 6}; cout << "The largest minimum distance possible is: " << largestMinimumDistance(numStalls, numCows, POS) << endl;} |

**Output**

The largest minimum distance possible is: 2 |

### Time Complexity - O(N * log(N))

where **‘N’ **is the number of elements in the given array/list.

We are calling the **isPossible()** function along with the binary search. The binary search takes **O(log(N))** time, and in each iteration, we call the **isPossible()** function having **O(N)** time complexity. So the total time complexity will be **O(N * log(N))**.

### Space Complexity - O(log(N))

where **‘N’ **is the number of elements in the given array/list.

The array, when sorted, will take **log(N)** space so that the overall space complexity will be **O(log(N))**.

## Key Takeaways

In this article, we solved a quite interesting problem: __Aggressive Cows__. For this question, it is very important to completely understand the problem statement, which we did by taking some examples. We discussed the naive approach first and then optimized the solution by __binary search__ as the problem had monotonic property.

With this problem, you must have got an idea of when to use __binary search__.

Some of the problems which you can practice based on a similar concept are-

__Understanding Binary Search Algorithm__(Magnetic Force Between Two Balls)__Capacity To Ship Packages Within D Days__

Need help with the Placements, Product based Tech Companies etc., Join our __free trials courses__ to__ practice exam problems__ at __Codestudio__.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our ** Online Mock Test Series** on

__CodeStudio__**now!**