Aggressive Cows – GeeksforGeeks

Given a sorted 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.

Examples: 

Input: N = 5, K = 3, arr[] = {1, 2, 4, 8, 9}
Output: 3
Explanation: We can place cow 1 at position 1, cow 2 at position 4 and cow 3 at position 9. So, the maximum possible minimum distance between two cows is 3.

Input: N = 6, K = 4, arr[] = {6, 7,  9, 11, 13, 15}
Output: 2
Explanation: We can place cow 1 at position 6, cow 2 at position 9 and  cow 4 at position 15. So, the maximum possible minimum distance between two cows is 2.

Naive Approach: The basic way to solve the problem is as follows:

The maximum distance possible between two cows can be the difference between the maximum and minimum element (Which is less than the maximum element of the array) of the array and the minimum possible distance can be 1.

Follow the steps to solve the problem:

• We will start iterating from 1 to the maximum element of the array and for each distance,  
  • We will check whether it is possible to place all the cows in the barn by maintaining this minimum distance.
• If it is possible then we will store it as a possible answer and continue to search for a better answer.
• Else, break the loop, and return the answer.

Illustration:

Consider: N = 5, K = 3, arr =  {1, 2, 4, 8, 9}.

• Maximum element = 9. So we will iterate between 1 to 9.
• At i = 1, we can place the cows at positions 1, 2, 4 maintaining the minimum distance of 1.
• At i = 2, we can place the cows at positions 1, 4, 8 maintaining the minimum distance of 2.
• At i = 3, we can place the cows at 1, 4, and 8 maintaining the minimum distance of 3.
• At i = 4, we can not place the cows by maintaining the minimum distance of 4.
• So, the largest possible distance is 3.

Below is the implementation of the above approach.

Time Complexity: O(N*(max element in the input array))
Auxiliary Space: O(1).

Efficient Approach: In the above approach, the search for the answer can be optimized using Binary search.

As we have seen in the case of brute force solution we are iterating from 1 to the maximum element of the array and at each distance, we check whether it can be our possible answer or not. Instead of doing this, we can run a binary search from 1 to the maximum element of the array.

Follow the steps to solve the problem:

• Apply a binary search between 1 and the maximum element of the array.
  • Each time find the middle element of the search space.
  •  If that middle element can be a possible minimum distance store it as a possibility until we find a better answer, then move in the right direction in the search space.
  • Else, we will move left in our search space.
• When the binary search is complete, return the answer.

Illustration:

Consider: N = 5, K =3, arr =  {1, 2, 4, 8, 9}.

• Maximum element = 9. So our search space will be 1 to 9.
• First, L = 1 and R = 9, mid = 5; we can not place the cows by maintaining the minimum distance of 5. So, we will move left in our search space.
• Now, L = 1 and R = 4, mid = 2; we can place the cows at positions 1, 4, and 8 maintaining the minimum distance of 2. So, we will store 2 as a possible answers and move right into our search space.
• Now, L=3 and R=4, mid = 3; we can place the cows at positions 1, 4, and 8 maintaining the minimum distance of 3. So, we will store 3 as a possible answers and move right into our search space.
• Now, L = 4 and R = 4, mid = 4; we can not place the cows by maintaining the minimum distance of 5. So, we will move left in our search space.
• Now, L = 4 and R = 3, Since, L > R, our binary search is complete, and the largest possible answer is 3.

Below is the implementation of the above approach.

Time Complexity: O(N * log(maximum element of the array ))
Auxiliary Space: O(1)

Given a sorted 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.

Examples: 

Input: N = 5, K = 3, arr[] = {1, 2, 4, 8, 9}
Output: 3
Explanation: We can place cow 1 at position 1, cow 2 at position 4 and cow 3 at position 9. So, the maximum possible minimum distance between two cows is 3.

Input: N = 6, K = 4, arr[] = {6, 7,  9, 11, 13, 15}
Output: 2
Explanation: We can place cow 1 at position 6, cow 2 at position 9 and  cow 4 at position 15. So, the maximum possible minimum distance between two cows is 2.

Naive Approach: The basic way to solve the problem is as follows:

The maximum distance possible between two cows can be the difference between the maximum and minimum element (Which is less than the maximum element of the array) of the array and the minimum possible distance can be 1.

Follow the steps to solve the problem:

• We will start iterating from 1 to the maximum element of the array and for each distance,  
  • We will check whether it is possible to place all the cows in the barn by maintaining this minimum distance.
• If it is possible then we will store it as a possible answer and continue to search for a better answer.
• Else, break the loop, and return the answer.

Illustration:

Consider: N = 5, K = 3, arr =  {1, 2, 4, 8, 9}.

• Maximum element = 9. So we will iterate between 1 to 9.
• At i = 1, we can place the cows at positions 1, 2, 4 maintaining the minimum distance of 1.
• At i = 2, we can place the cows at positions 1, 4, 8 maintaining the minimum distance of 2.
• At i = 3, we can place the cows at 1, 4, and 8 maintaining the minimum distance of 3.
• At i = 4, we can not place the cows by maintaining the minimum distance of 4.
• So, the largest possible distance is 3.

Below is the implementation of the above approach.

Time Complexity: O(N*(max element in the input array))
Auxiliary Space: O(1).

Efficient Approach: In the above approach, the search for the answer can be optimized using Binary search.

As we have seen in the case of brute force solution we are iterating from 1 to the maximum element of the array and at each distance, we check whether it can be our possible answer or not. Instead of doing this, we can run a binary search from 1 to the maximum element of the array.

Follow the steps to solve the problem:

• Apply a binary search between 1 and the maximum element of the array.
  • Each time find the middle element of the search space.
  •  If that middle element can be a possible minimum distance store it as a possibility until we find a better answer, then move in the right direction in the search space.
  • Else, we will move left in our search space.
• When the binary search is complete, return the answer.

Illustration:

Consider: N = 5, K =3, arr =  {1, 2, 4, 8, 9}.

• Maximum element = 9. So our search space will be 1 to 9.
• First, L = 1 and R = 9, mid = 5; we can not place the cows by maintaining the minimum distance of 5. So, we will move left in our search space.
• Now, L = 1 and R = 4, mid = 2; we can place the cows at positions 1, 4, and 8 maintaining the minimum distance of 2. So, we will store 2 as a possible answers and move right into our search space.
• Now, L=3 and R=4, mid = 3; we can place the cows at positions 1, 4, and 8 maintaining the minimum distance of 3. So, we will store 3 as a possible answers and move right into our search space.
• Now, L = 4 and R = 4, mid = 4; we can not place the cows by maintaining the minimum distance of 5. So, we will move left in our search space.
• Now, L = 4 and R = 3, Since, L > R, our binary search is complete, and the largest possible answer is 3.

Below is the implementation of the above approach.

Time Complexity: O(N * log(maximum element of the array ))
Auxiliary Space: O(1)