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 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 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] = {42136};

    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

  1. The range of the distance between any two cows is [1, max(POS)-min(POS)]
  2. Initialize low=1 and high = max(POS)-min(POS)
  3. Find mid = (low+high)/2.  
  4. Check if it is possible to place the cows such that the minimum distance is equal to mid. 
    1. 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.
    2. 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.
  5. 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] = {42136};

    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-  

 

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!
 

Was this article helpful ?
3 upvotes