Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Aggressive Cows

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
884 upvotes
Asked in companies
AdobeGoldman SachsDunzo

Problem statement

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.



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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
6 4
0 3 4 7 10 9


Sample Output 1 :
3


Explanation to Sample Input 1 :
The maximum possible minimum distance between any two cows will be 3 when 4 cows are placed at positions {0, 3, 7, 10}. Here distance between cows are 3, 4 and 3 respectively.


Sample Input 2 :
5 2
4 2 1 3 6


Sample Output 2 :
5


Expected time complexity:
Can you solve this in O(n * log(n)) time complexity?


Constraints :
2 <= 'n' <= 10 ^ 5
2 <= 'k' <= n
0 <= 'arr[i]' <= 10 ^ 9
Time Limit: 1 sec.
Hint

Place all the ‘k’ cows in the ‘n’ stalls such that the minimum distance between any two of them is as large as possible.

Approaches (2)
Naive Approach

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.

Time Complexity

O(n ^ 2), where ‘n’ is the number of elements in the given array.

We are applying a check() function along with the binary search. So the total time complexity will be 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 the overall space complexity will be O(log(n)).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Aggressive Cows
All tags
Sort by
Search icon

Interview problems

C++ Solution || Binary Search Approach || All Test Case Pass || Fastest Runtime 15 ms

bool isPossible(vector<int> &stalls, int k, int mid) {

  int cowCount = 1;

  int lastPos = stalls[0];

 

  for (int i = 0; i < stalls.size(); i++) {

    if (stalls[i] - lastPos >= mid) {

      cowCount++;

      if (cowCount == k) {

        return true;

      }

      lastPos = stalls[i];

    }

  }

  return false;

}

 

int aggressiveCows(vector<int> &stalls, int k) {

  sort(stalls.begin(), stalls.end());

 

  int s = 0;

  int maxi = -1;

 

  for (int i = 0; i < stalls.size(); i++) {

    maxi = max(maxi, stalls[i]);

  }

 

  int e = maxi;

  int ans = -1;

  int mid = s + (e - s) / 2;

 

  while (s <= e) {

    if (isPossible(stalls, k, mid)) {

      ans = mid;

      s = mid + 1;

    } else {

      e = mid - 1;

    }

    mid = s + (e - s) / 2;

  }

  return ans;

}

41 views
0 replies
1 upvote

Interview problems

c++ binary search easy solution.

int ispossible(vector<int> &stalls, int k, int mid){

    int cowCount =1;

    int lastpos=stalls[0];

    for(int i=0; i<stalls.size(); i++){

        if(stalls[i]-lastpos>=mid){

            cowCount++;

            if(cowCount==k){

                return true;

            }

            lastpos = stalls[i];

        }

    }

    return false;

}

int aggressiveCows(vector<int> &stalls, int k)

{   sort(stalls.begin(),stalls.end());

   int s=0;

   int maxi=-1;

   int ans=-1;

   for (int i = 0; i < stalls.size(); i++) {

      maxi = max(maxi, stalls[i]);

 

   }

   int e = maxi;

   int mid = s+(e-s)/2;

   while(s<=e){

       if(ispossible(stalls,k,mid)){

           ans = mid;

           s = mid+1;

       }

       else{

           e = mid-1;

       }

       mid = s+(e-s)/2;

   }

    return ans;

}

29 views
0 replies
0 upvotes

Interview problems

Simple 🧠 || java || 100% easy || Binary Search

import java.util.*;
public class Solution {
   public static   boolean cowStalls(int arr[],int dist,int cows)
    {
        int countCows=1;
        int lastCow=arr[0];
        for(int i=1;i<arr.length;i++)
        {
            if(arr[i]-lastCow>=dist)
            {
                countCows++;
                lastCow=arr[i];
            }
            if(countCows>=cows)
            {
                return true;
            }
        }
        return false;
    }
    public static int aggressiveCows(int []stalls, int k) {
        //    Write your code here.
    int size=stalls.length;
        Arrays.sort(stalls);
        // int min=-1;
        int limit=stalls[size-1]-stalls[0];
    int left=1;
    int ans=-1;
    int right=limit;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(cowStalls(stalls,mid,k)==true)
        {
            ans=mid;
             left=mid+1;
            
        }
        else{
           right=mid-1;
        }
    }
    return ans;

    }
}
28 views
0 replies
0 upvotes

Interview problems

BRUTE FORCE O(N2 + NlogN)

bool canWePlace(vector<int> stalls, int dist, int cows){

    int cowcount=1;int lastCowPos=stalls[0];

    for( int i =1 ; i< stalls.size() ; i++ ){

        if(stalls[i]-lastCowPos >= dist){

            cowcount++;

            lastCowPos=stalls[i];

            if(cowcount==cows) break;

        }

    }

    if(cowcount >=  cows) return true;

    else return false;

}

int aggressiveCows(vector<int> &stalls, int k)

{

    //    Write your code here.

    sort(stalls.begin(), stalls.end());

    int n = stalls.size();

    int maxi = stalls[n-1];

    int mini = stalls[0];

    int ans=1;

    for(int i = 1 ; i <= maxi-mini ; i++){

        if(canWePlace(stalls,i,k) == true) ans=i;

       

    }

    return ans ;

}

28 views
0 replies
0 upvotes

Interview problems

Aggressive Cows || Binary Search on Answer || C++ solution

bool isPossible(vector<int>&arr,int k,int mid){
    int lastPos =arr[0];
    int cow =1;
    for(int i=1;i<arr.size();i++){
        int dist =arr[i]-lastPos;
        if(dist >=mid){
            cow++;
            lastPos =arr[i];
        }
    }
    return cow>=k;
}

int aggressiveCows(vector<int> &stalls, int k)
{
    sort(stalls.begin(),stalls.end());
     int s =1;
     int n =stalls.size()-1;
     int e =stalls[n]-stalls[0];
     int ans =-1;
     while(s<=e){
         int mid =s+(e-s)/2;
         if(isPossible(stalls,k,mid)){
             ans =mid;
             s =mid+1;
         }
         else{
             e =mid-1;
         }
     }
    return ans;
}
71 views
0 replies
0 upvotes

Interview problems

very easy C++ solution

bool ispossible(vector<int> &stalls, int k, int mid) 

{

    int cowcount=1;

    int currentPosition=stalls[0];

    for(int i=1;i<stalls.size();i++)

    {

        if(stalls[i]-currentPosition>=mid)

        {

            cowcount++;

            if(cowcount==k)

            {

                return true;

            }

            currentPosition=stalls[i];

        }

    }

    return false;

}

int aggressiveCows(vector<int> &stalls, int k)

{

    //    Write your code here.

    sort(stalls.begin(),stalls.end());

    int s=0;

    int n=stalls.size();

    int e=stalls[n-1]-stalls[0];

    int ans=-1;

    while(s<=e)

    {

        int mid=(s+e)/2;

        if(ispossible(stalls,k,mid))

        {

            ans=mid;

            s=mid+1;

        }

        else{

            e=mid-1;

        }

    }

    return ans;

}

40 views
1 reply
0 upvotes

Interview problems

C++ Code Solution with Binary Search technique

Return high at the end because it will points to the maximum possible value , when the while loop is over.

 

bool canweplace(vector<int>&stalls , int cows , int dist){
    int n = stalls.size();
    int cntcows = 1;
    int last = stalls[0];
    for(int i = 0 ;i<n ;i++){
        if(stalls[i]-last >= dist){
            cntcows++;
            last = stalls[i];
        }
        if(cntcows >= cows) return true;
    }
    return false;
}

int aggressiveCows(vector<int> &stalls, int k)
{
    int n = stalls.size();
    sort(stalls.begin(),stalls.end());
    int low = 1 ;
    int high = stalls[n-1] - stalls[0];
    while(low<=high){
        int mid = (low+high)/2;
        if(canweplace(stalls, k , mid)){
            low = mid+1;
        }
        else{
            high = mid-1;
        }
    }
    return high;
}
145 views
0 replies
1 upvote

Interview problems

Simple and Easy solution...

import java.util.Arrays;

 

public class Solution {

    public static int aggressiveCows(int[] stalls, int k) {

        // Write your code here.

        Arrays.sort(stalls);

        int n = stalls.length;

        int start = 0;

        int end = stalls[n - 1] - stalls[0];

        int ans = 0, mid;

 

        while (start <= end) {

            mid = start + (end - start) / 2;

 

            int pos = stalls[0];

            int count = 1;

            for (int i = 0; i < n; i++) {

                if (pos + mid <= stalls[i]) {

                    count++;

                    pos = stalls[i];

                }

            }

 

            if (count < k) {

                end = mid - 1;

            } else {

                start = mid + 1;

                ans = mid;

            }

        }

 

        return ans;

    }

}

108 views
0 replies
0 upvotes

Interview problems

Better than 99.93% | CPP | Binary Search & Recursion

bool isPossibleSolution(vector<int> &stalls, int k, int mid){

    int numCow = 1;

    int initialPos = stalls[0];

    for(int i=1; i<stalls.size(); i++){

        if(stalls[i]-initialPos>=mid){

            initialPos=stalls[i];

            numCow++;

            

        }

        if(numCow>=k) return true;

    }

    return false;

}

 

int checkPossibleAnswer(vector<int> &stalls, int k, int s, int e, int ans){

    if(s>e){

        return ans;

    }

    int mid = s+(e-s)/2;

 

    if(isPossibleSolution(stalls, k, mid)){

        ans = mid;

        checkPossibleAnswer(stalls, k, mid+1, e, ans);

    }else{

        checkPossibleAnswer(stalls, k, s, mid-1, ans);

    }

}

 

int aggressiveCows(vector<int> &stalls, int k)

{

    //    Write your code here.

    sort(stalls.begin(), stalls.end());

    int s = 1;

    int e = stalls[stalls.size()-1] - stalls[0];

    return checkPossibleAnswer(stalls, k, s, e, -1);

 

}

55 views
0 replies
0 upvotes

Interview problems

Best Solution

TC = O(logn)

SC = O(1)

 

 

bool solve(int gap , int k, vector<int>&arr){

    int prev = arr[0];

    k--;

    for(int i =1 ;i<arr.size() ;++i){

        if(arr[i]-prev>=gap){

            k--; 

            prev= arr[i]; 

        }

        if(k==0) return true;

    }

    return false;

}

 

int aggressiveCows(vector<int> &stalls, int k)

{

    sort(stalls.begin(),stalls.end()) ;

    int n = stalls.size(); 

    int l =1 ;

    int r = stalls[n-1]-stalls[0]; // this is max possible distance

 

    int ans =0 ;

    while(l<=r){

        int m = l+(r-l)/2; 

        if(solve(m,k,stalls)){

            ans =m;

            l= m+1;

        }else{

            r = m-1;

        }

    }

    return ans; 

}

25 views
0 replies
0 upvotes
Full screen
Console