# Aggressive Cows (On Binary Search)

Here, we are discussing problem named **Aggressive Cows based on Binary and its solution**.

Submitted by Indrajeet Das, on October 23, 2018

A farmer has built a long barn with **N** stalls. The stalls are placed in a straight manner at positions from **x1, x2, ...xN**. But his cows (C) are aggressive and don’t want to be near other cows. To prevent cows from hurting each other, he wants to place them in such a way so that the minimum distance between them is as large as possible. What is the largest minimum distance?

**Constraints:**

N: 2<=N<=100,000 C: 2<=C<=N Xi: 0<=Xi<=1,000,000,000

**Input:**

Line1: Two integers N and C Next N lines: An integer for Xi stall's position

**Example:**

Input: 5 3 1 2 4 8 9 Output: 3

**Explanation:**

If the cows are placed at 1,4 and 9, it will result in minimum distance from 3.

**SOLUTION AND CODE**

Since the range of xi is from 0 to 10^9, one can say that the minimum distance between the cows will lie between the range. The minimum distance between 2 stalls can be 0 (lower bound) and maximum distance is 10^9 (upper bound). So, one can check for each value from lower bound to upper bound.

Let's say for k minimum distance, we can check if it is possible to place cows in the stall. In case, you have reached the last stall but didn’t have placed all cows, then it is not possible else it is possible.

A point to note is that if, for a k, it is possible to place the cows. Then all the values less than k will be true. Also, if k is false, then all the values greater than k will be false. We can say it is creating a monotonic function and we have to check for the transition from true to false and return that value.

It can be quickly and easily done with Binary Search from the range of 0 to 10^9.

**CODE**

#include <bits/stdc++.h> using namespace std; int N,C; int check(int num,int stalls[]) { int cows=1,pos=stalls[0]; for (int i=1; i<N; i++) { if (stalls[i]-pos>=num) { pos=stalls[i]; cows++; if (cows==C) return 1; } } return 0; } int binarySearch(int stalls[]) { int start=0,end=stalls[N-1],max=-1; while (end>start) { int mid=(start+end)/2; if (check(mid,stalls)==1) { if (mid>max) max=mid; start=mid+1; } else end=mid; } return max; } int main() { int t; cin>>t; while (t--) { cin>>N>>C; int stalls[N]; for (int i=0; i<N; i++) cin>>stalls[i]; sort(stalls,stalls+N); int k=binarySearch(stalls); cout<<k; } return 0; }

**Output**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions