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.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check whether a distance is// keeping all the cows in the barnbool ok(vector<int>& v, int x, int c){ int n = v.size(); int count = 1; int d = v[0]; for (int i = 1; i < n; i++) { if (v[i] - d >= x) { d = v[i]; count++; } else { continue; } } if (count >= c) { return true; } return false;}// Function to find the maximum possible// minimum distance between two cowsint aggressive_cows(vector<int>& v, int n, int k){ long long ans = -1; int maxi = 0; for (int i = 0; i < n; i++) { maxi = max(maxi, v[i]); } // Loop from 1 to max limit of the // barn length (here = 10^9) for (long long i = 1; i <= maxi; i++) { if (ok(v, i, k)) { ans = i; } else { break; } } return ans;}// Driver codeint main(){ int K = 3; vector<int> arr = { 1, 2, 4, 8, 9 }; int N = arr.size(); // Function call int ans = aggressive_cows(arr, N, K); cout << ans << endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;public class Main { // Driver code public static void main(String[] args) { int K = 3; int[] arr = { 1, 2, 4, 8, 9 }; int N = arr.length; // Function call System.out.println(aggressive_cows(arr, N, K)); } // Function to check whether a distance is // keeping all the cows in the barn public static boolean ok(int[] v, int x, int c) { int n = v.length; int count = 1; int d = v[0]; for (int i = 1; i < n; i++) { if (v[i] - d >= x) { d = v[i]; count++; } else { continue; } } if (count >= c) { return true; } return false; } // Function to find the maximum possible // minimum distance between two cows public static int aggressive_cows(int[] v, int n, int k) { long ans = -1; int maxi = 0; for (int i = 0; i < n; i++) { maxi = Math.max(maxi, v[i]); } // Loop from 1 to max limit of the // barn length (here = 10^9) for (long i = 1; i <= maxi; i++) { if (ok(v, (int)i, k)) { ans = i; } else break; } return (int)ans; }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
# Python code to implement the approach# Function to check whether a distance is# keeping all the cows in the barndef ok(v,x,c): n=len(v) count=1 d=v[0] for i in range(1,n): if(v[i]-d>=x): d=v[i] count=count+1 else: continue if(count>=c): return True return False # Function to find the maximum possible# minimum distance between two cowsdef aggressive_cows(v,n,k): ans=-1 maxi=0 for i in range(n): maxi=max(maxi,v[i]) # Loop from 1 to max limit of the # barn length (here = 10^9) for i in range(1,maxi+1): if(ok(v,i,k)): ans=i else: break return ans # Driver codeK=3arr=[1,2,4,8,9]N=len(arr)# Function callans=aggressive_cows(arr,N,K)print(ans)# This code is contributed by Pushpesh Raj. |
C#
// C# code to implement the approachusing System;class Program { // Driver code static void Main(string[] args) { int K = 3; int[] arr = { 1, 2, 4, 8, 9 }; int N = arr.Length; // Function call Console.WriteLine(aggressive_cows(arr, N, K)); } // Function to check whether a distance is // keeping all the cows in the barn public static bool ok(int[] v, int x, int c) { int n = v.Length; int count = 1; int d = v[0]; for (int i = 1; i < n; i++) if (v[i] - d >= x) { d = v[i]; count++; } else continue; if (count >= c) return true; return false; } // Function to find the maximum possible // minimum distance between two cows public static int aggressive_cows(int[] v, int n, int k) { long ans = -1; int maxi = 0; for (int i = 0; i < n; i++) maxi = Math.Max(maxi, v[i]); // Loop from 1 to max limit of the // barn length (here = 10^9) for (long i = 1; i <= maxi; i++) if (ok(v, (int)i, k)) ans = i; else break; return (int)ans; }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code for the above approach // Function to check whether a distance is // keeping all the cows in the barn function ok(v, x, c) { let n = v.length; let count = 1; let d = v[0]; for (let i = 1; i < n; i++) { if (v[i] - d >= x) { d = v[i]; count++; } else { continue; } } if (count >= c) { return true; } return false; } // Function to find the maximum possible // minimum distance between two cows function aggressive_cows(v, n, k) { let ans = -1; let maxi = 0; for (let i = 0; i < n; i++) { maxi = Math.max(maxi, v[i]); } // Loop from 1 to max limit of the // barn length (here = 10^9) for (let i = 1; i <= maxi; i++) { if (ok(v, i, k)) { ans = i; } else { break; } } return ans; } // Driver code let K = 3; let arr = [1, 2, 4, 8, 9]; let N = arr.length; // Function call let ans = aggressive_cows(arr, N, K); console.log(ans);// This code is contributed by Potta Lokesh |
Output
3
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.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to position the cow x distance apartbool ok(vector<int>& v, int x, int c){ int n = v.size(); // We already place it at the first // available slot i.e v[0](Greedy) int count = 1; int d = v[0]; for (int i = 1; i < n; i++) { if (v[i] - d >= x) { d = v[i]; count++; } else { continue; } } if (count >= c) { return true; } return false;}// Function to find the maximum possible// minimum distance between the cowsint aggressive_cows(vector<int>& v, int n, int k){ // Just take l = 1 and high = 1000000 // or any large number int l = 1; int r = 1e9; int ans = -1; // Applying Binary search while (r >= l) { int mid = l + (r - l) / 2; if (ok(v, mid, k)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans;}// Driver codeint main(){ int K = 3; vector<int> arr = { 1, 2, 8, 4, 9 }; int N = arr.size(); // Function call int ans = aggressive_cows(arr, N, K); cout << ans << endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { // Function to check if it is possible // to position the cow x distance apart static boolean ok(int[] v, int x, int c) { int n = v.length; // We already place it at the first // available slot i.e v[0](Greedy) int count = 1; int d = v[0]; for (int i = 1; i < n; i++) { if (v[i] - d >= x) { d = v[i]; count++; } else { continue; } } if (count >= c) { return true; } return false; } // Function to find the maximum possible // minimum distance between the cows static int aggressive_cows(int[] v, int n, int k) { // Just take l = 1 and high = 1000000 // or any large number int l = 1; int r = 1000000000; int ans = -1; // Applying Binary search while (r >= l) { int mid = l + (r - l) / 2; if (ok(v, mid, k)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } // Driver code public static void main(String[] args) { int K = 3; int[] arr = new int[] { 1, 2, 8, 4, 9 }; int N = arr.length; // Function call System.out.println(aggressive_cows(arr, N, K)); }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
# Python code to implement the approach# Function to check if it is possible# to position the cow x distance apartdef ok(v, x, c): n = len(v) # We already place it at the first # available slot i.e v[0](Greedy) count = 1 d = v[0] for i in range(1, n): if (v[i] - d >= x): d = v[i] count += 1 else: continue if (count >= c): return True return False# Function to find the maximum possible# minimum distance between the cowsdef aggressive_cows(v, n, k): # Just take l = 1 and high = 1000000 # or any large number l = 1 r = 1000000000 ans = -1 # Applying Binary search while (r >= l): mid = l + (r - l)//2 if (ok(v, mid, k)): ans = mid l = mid + 1 else: r = mid - 1 return ans# Driver Codeif __name__ == '__main__': K = 3 arr = [1, 2, 8, 4, 9] N = len(arr) # Function call print(aggressive_cows(arr, N, K))# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code to implement the approachusing System;class Program { // Function to check if it is possible // to position the cow x distance apart static bool ok(int[] v, int x, int c) { int n = v.Length; // We already place it at the first // available slot i.e v[0](Greedy) int count = 1; int d = v[0]; for (int i = 1; i < n; i++) { if (v[i] - d >= x) { d = v[i]; count++; } else continue; } if (count >= c) return true; return false; } // Function to find the maximum possible // minimum distance between the cows static int aggressive_cows(int[] v, int n, int k) { // Just take l = 1 and high = 1000000 // or any large number int l = 1; int r = 1000000000; int ans = -1; // Applying Binary search while (r >= l) { int mid = l + (r - l) / 2; if (ok(v, mid, k)) { ans = mid; l = mid + 1; } else r = mid - 1; } return ans; } // Driver code public static void Main() { int K = 3; int[] arr = new int[] { 1, 2, 8, 4, 9 }; int N = arr.Length; // Function call Console.WriteLine(aggressive_cows(arr, N, K)); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code to implement the approach// Function to check if it is possible// to position the cow x distance apartfunction ok(v, x, c) { var n = v.length; // We already place it at the first // available slot i.e v[0](Greedy) var count = 1; var d = v[0]; for (var i = 1; i < n; i++) { if (v[i] - d >= x) { d = v[i]; count++; } else { continue; } } if (count >= c) { return true; } return false;}// Function to find the maximum possible// minimum distance between the cowsfunction aggressive_cows(v, n, k) { // Just take l = 1 and high = 1000000 // or any large number var l = 1; var r = 1e9; var ans = -1; // Applying Binary search while (r >= l) { var mid = (l + (r - l) / 2) | 0; if (ok(v, mid, k)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans;}// Driver codevar K = 3;var arr = [1, 2, 8, 4, 9];var N = arr.length;// Function callvar ans = aggressive_cows(arr, N, K);console.log(ans);// This code is contributed by Tapesh(tapeshdua420) |
Output
1
Time Complexity: O(N * log(maximum element of the array ))
Auxiliary Space: O(1)
More Efficient Approach:
As we have seen in the case of brute force solution we are iterating from 0 to the maximum element of the array and at each distance, we check whether it can be our possible answer or not.
In Efficient Process we can run a binary search from 0 to the maximum element in the array.
But more than all we can run binary search from 0 to Maximum difference of the array.
In sorted array is A[N-1] – A[0] (last – first element in the array) is the maximum difference possible. It works perfectly fine, as our search space is that only, we can never get a difference that is greater than this.
This saves a lot of iterations in many cases, one such example is
- Arr = [70, 70, 70, 70] N=4, K=3
- Here Efficient method runs binary search from 0 to 70.
- More Efficient method (this method) runs binary search from 0 to 0. (A[N-1] – A[0] = 0)
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to position the cow x distance apartbool ok(vector<int>& v, int x, int c){ int n = v.size(); // We already place it at the first // available slot i.e v[0](Greedy) int count = 1; int last = 0; for (int i = 0; i < n; i++) { if (v[i] - v[last] >= x) { last = i; //cow placed count++; } if (count >= c) { return true; } } return false;}// Function to find the maximum possible// minimum distance between the cowsint aggressive_cows(vector<int>& v, int n, int k){ // Just take l = 1 and high = M (MAX DIFF POSSIBLE) // M = last - first element in sorted array int l = 0; int r = v[n-1] - v[0]; int ans = -1; // Applying Binary search while (l<=r) { int mid = l + (r - l) / 2; if (ok(v, mid, k)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans;}// Driver codeint main(){ int K = 3; vector<int> arr = { 1, 2, 4, 8, 9 }; int N = arr.size(); // Function call int ans = aggressive_cows(arr, N, K); cout << ans << endl; return 0;}//Code contributed by Balakrishnan R (rbkraj000) |
Java
//Java code for the above approachimport java.util.Vector;class GFG { // Function to check if it is possible // to position the cow x distance apart static boolean ok(Vector<Integer> v, int x, int c) { int n = v.size(); // We already place it at the first // available slot i.e v[0](Greedy) int count = 1; int last = 0; for (int i = 0; i < n; i++) { if (v.get(i) - v.get(last) >= x) { last = i; //cow placed count++; } if (count >= c) { return true; } } return false; } // Function to find the maximum possible // minimum distance between the cows static int aggressive_cows(Vector<Integer> v, int n, int k) { // Just take l = 1 and high = M (MAX DIFF POSSIBLE) // M = last - first element in sorted array int l = 0; int r = v.get(n-1) - v.get(0); int ans = -1; // Applying Binary search while (l <= r) { int mid = l + (r - l) / 2; if (ok(v, mid, k)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; }//Driver code public static void main(String[] args) { int K = 3; Vector<Integer> arr = new Vector<Integer>(); arr.add(1); arr.add(2); arr.add(4); arr.add(8); arr.add(9); int N = arr.size(); // Function call int ans = aggressive_cows(arr, N, K); System.out.println(ans); }} |
Python3
# Python code to implement the approachimport math# Function to check if it is possible# to position the cow x distance apartdef ok(v, x, c): n = len(v); # We already place it at the first # available slot i.e v[0](Greedy) count = 1; last = 0; for i in range(0,n): if (v[i] - v[last] >= x) : last = i; #cow placed count+=1; if (count >= c) : return True; return False;# Function to find the maximum possible# minimum distance between the cowsdef aggressive_cows(v, n, k): # Just take l = 1 and high = M (MAX DIFF POSSIBLE) # M = last - first element in sorted array l = 0; r = v[n-1] - v[0]; ans = -1; # Applying Binary search while (l<=r): mid = l + math.floor((r - l) / 2); if (ok(v, mid, k)): ans = mid; l = mid + 1; else : r = mid - 1; return ans;# Driver codeK = 3;arr = [ 1, 2, 4, 8, 9 ];N = len(arr);# Function callans = aggressive_cows(arr, N, K);print(ans);# This code is contributed by ritaagarwal. |
Javascript
// Javascript code to implement the approach// Function to check if it is possible// to position the cow x distance apartfunction ok(v, x, c){ let n = v.length; // We already place it at the first // available slot i.e v[0](Greedy) let count = 1; let last = 0; for (let i = 0; i < n; i++) { if (v[i] - v[last] >= x) { last = i; //cow placed count++; } if (count >= c) { return true; } } return false;}// Function to find the maximum possible// minimum distance between the cowsfunction aggressive_cows(v, n, k){ // Just take l = 1 and high = M (MAX DIFF POSSIBLE) // M = last - first element in sorted array let l = 0; let r = v[n-1] - v[0]; let ans = -1; // Applying Binary search while (l<=r) { let mid = l + Math.floor((r - l) / 2); if (ok(v, mid, k)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans;}// Driver codelet K = 3;let arr = [ 1, 2, 4, 8, 9 ];let N = arr.length;// Function calllet ans = aggressive_cows(arr, N, K);console.log(ans); // This code is contributed by poojaagarwal2. |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if it is possible // to position the cow x distance apart static bool ok(List<int> v, int x, int c) { int n = v.Count; // We already place it at the first // available slot i.e v[0](Greedy) int count = 1; int last = 0; for (int i = 0; i < n; i++) { if (v[i] - v[last] >= x) { last = i; //cow placed count++; } if (count >= c) { return true; } } return false; } // Function to find the maximum possible // minimum distance between the cows static int aggressive_cows(List<int> v, int n, int k) { // Just take l = 1 and high = M (MAX DIFF POSSIBLE) // M = last - first element in sorted array int l = 0; int r = v[n-1] - v[0]; int ans = -1; // Applying Binary search while (l<=r) { int mid = l + (r - l) / 2; if (ok(v, mid, k)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } // Driver code static public void Main() { int K = 3; List<int> arr = new List<int>{ 1, 2, 4, 8, 9 }; int N = arr.Count; // Function call int ans = aggressive_cows(arr, N, K); Console.Write(ans); }} |
Output
3
Time Complexity: O(N * log(M))
- N = Size of the array.
- M = A[N-1] – A[0] (last – first element) Maximum possible difference in the array.
Auxiliary Space: O(1)
The above More Efficient Method Idea, Algorithm, and Code are contributed by Balakrishnan R (rbkraj000 – GFG ID). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
