What is the AGGRCOW Problem?

Aggressive cow problem is a tough nut to crack in programming as well as your real life!!

This is one of the most advanced problems related to the application of binary search. The aggressive cow question is therefore generally every interviewer’s favorite. This is because to solve this problem, you need to know the basic application and concept of binary search.

But how do you actually resolve the aggressive cows problem?

Well, the answer is obvious: Using Binary Search!!

Still not sure how to find the solution? Stick to this post to learn. 

Here is everything you need to know about the aggressive cows problem and its solution. 

 

The Problem Statement

Before understanding the solution to the problem, let’s first understand the problem statement. The problem statement goes like this:

John, the farmer, has constructed a new barn consisting of N stalls. He has built all these stalls in a single line X.

In his barn, he has a C number of cows. His cows are disappointed with the new barn and have become very aggressive. Farmer John wishes to place the cows in the stalls in such a way that the cows have the largest minimum distance. 

You are required to write a code to find the required largest minimum distance.

Input:

T: It is the total number of test cases. All the test cases will follow:

Line 1: There are two space integers: C and N.

Line 2: N+1: line i+1 depicts the location of stall location which is xi.

Output:

Each test case should output one integer which is the largest minimum distance between the cows.

If you are still not able to understand the problem, let’s consider the following example:

Input:

1

5 3

1

2

8

4

9

The output of the code will be:

3

Output Explanation: 

Farmer John can put the cows in stalls at positions 1, 8, and 4. This will print the minimum distance between the cows as 3.

Let’s Proceed With The Solution

So, now you may have got an idea of what the aggressive cows problem is. Let’s understand the solution to this problem in detail.

Now that we know that the value of xi ranges from 0 to 10^9. Therefore, the minimum distance will lie within this range only. You can say that the minimum distance between any two 2 stalls can be as low as 0 and as high as 10^9.

Hence, you can check for each value between the lower and upper bound. Let’s assume the minimum distance is K. We will have to check if we can place a cow in that stall or not. If you are at the last stall and you have not placed all the cows. This simply means that the solution you are using is not feasible.

Read More