Last Updated: 10 Jan, 2021
Aggressive Cows
Moderate
Asked in companies
You are given an array 'arr' consisting of 'n' integers which denote the position of a stall.
You are also given an integer 'k' which denotes the number of aggressive cows.
You are given the task of assigning stalls to 'k' cows such that the minimum distance between any two of them is the maximum possible.
Print the maximum possible minimum distance.
Example:
Input: 'n' = 3, 'k' = 2 and 'arr' = {1, 2, 3}
Output: 2
Explanation: The maximum possible minimum distance will be 2 when 2 cows are placed at positions {1, 3}. Here distance between cows is 2.
Input format :
The first line contains two integers ‘n’ and ‘k’ denoting the number of elements in the array and the number of aggressive cows.
The second line contains ‘n’ single space-separated integers denoting the position of the stalls.
Output format :
Return the largest possible minimum distance between cows.
Note :
You do not need to print anything; it has already been handled.
Approaches
What we are looking for is that we need to place all the ‘k’ cows in the ‘n’ stalls such that the minimum distance between any two of them is as large as possible.
We need to define a check() function that checks if a distance ‘x’ is possible between each of the cows. We can use a greedy approach here by placing cows at the leftmost possible stalls such that they are at least 'x' distance away from the last-placed cow.
We need to sort the given array/list so once we have our sorted array, we can apply the whole array of the sorted input, and use our function check(x) to find the largest distance possible. And as soon as you reach a position from where it’s not possible to find a distance from which cows could be safe so we basically break the loop.
What we are looking for is that we need to place all the ‘k’ cows in the ‘n’ stalls such that the minimum distance between any two of them is as large as possible.
We need to define a check() function that checks if a distance 'x' is possible between each of the cows. We can use a greedy approach here by placing cows at the leftmost possible stalls such that they are at least ‘x’ distance away from the last-placed cow.
We need to sort the given array/list so once we have our sorted array, we can apply the Binary Search algorithm on the sorted input, and use our function check(x) to find the largest distance possible.
Steps are as follows :
- First of all, consider low and high values for the starting and ending positions of the given array/list.
- Let mid be the minimum distance. Check in the sorted array how many positions are available so that the minimum distance between them is this mid.
- Now how to do that? Start with the least value in the array and keep ignoring all the elements until you get a difference between the lower element and the current element >= mid or you run out of elements.
- Use this idea to find the count of such possible positions. Now if this count is >= c then we already have a possible solution so store it and we now eliminate it from our search space by making low as mid + 1, otherwise, we don't store the result as it is not our solution and eliminate it from our search space by making high as mid - 1.
- Now our only objective is to find the maximum from all the results we have stored until our search space has exhausted.
Similar problems