AGGRCOW - Aggressive cows is a good question based on Binary Search! (It took me an hour to figure out, how to crack this nut using binary search :P )
Now let us talk about the question. In the problem statement it is given that N (2 <= N <= 100,000) and
x1,...,xN (0 <= xi <= 1,000,000,000). This makes one thing very obvious that the maximum possible ans is 1,000,000,000 and the minimum possible answer is 1.
We have got our upper and lower limits, and now we have to find the answer, which exist between them.
But the question arises, why binary search? It is very clear that, for a value 'x', if it is not possible to keep all the cows in the stalls with the minimum distance between any two cows as 'x', then it will not be possible for all y > x , and hence answer<x. This is the point which gives entry to binary search in the scene!
Now, we will do binary search for answer, with i as upper and j as lower limit, mid is the middle element. For each mid we will see if it is possible to fit all the cows in stalls with mid as the minimum distance between any two cows. Further we can decide if we have to search for the answer in the upper or lower half of the mid!
If you find any difficulty in coding part, refer to the following code!
Happy Coding! :)
My solution's complexity is O(n logn).
If you haven't done a lot of problems based on binary search, then this problem will make you learn something good!
Now let us talk about the question. In the problem statement it is given that N (2 <= N <= 100,000) and
x1,...,xN (0 <= xi <= 1,000,000,000). This makes one thing very obvious that the maximum possible ans is 1,000,000,000 and the minimum possible answer is 1.
We have got our upper and lower limits, and now we have to find the answer, which exist between them.
But the question arises, why binary search? It is very clear that, for a value 'x', if it is not possible to keep all the cows in the stalls with the minimum distance between any two cows as 'x', then it will not be possible for all y > x , and hence answer<x. This is the point which gives entry to binary search in the scene!
Now, we will do binary search for answer, with i as upper and j as lower limit, mid is the middle element. For each mid we will see if it is possible to fit all the cows in stalls with mid as the minimum distance between any two cows. Further we can decide if we have to search for the answer in the upper or lower half of the mid!
If you find any difficulty in coding part, refer to the following code!
Happy Coding! :)
Can You Give a Elaborate Solution
ReplyDeleteNO!
DeleteWhich part is not clear?
DeleteWhat is the entire thing with mid?
DeleteIf 'i' is the upper limit then how can i<=j??
ReplyDelete