I am unable to understand the solution for aggressive cows problem

#1

I am unable to understand the solution for aggressive cows problem. I have understood the problem but I am neither able to code nor able to understand the solution.

  1. Why we have put the condition in the loop (s+1)<e.
  2. Why we are putting s = mid instead of mid+1
  3. Why we are putting e = mid instead of mid-1
#2

@ap8730390
Instead of straight away going to the solution , first develop the intuition behind it.
First question is why binary search?
So if for a distance x if we are not able to place all the given cows x distances apart, that means for distances > x also we will not be able to place it, so all those values will be cut out i.e for the search space >= x the answer will be false.

Similarly if we are able to place all the cows for a distance x that means we will be able to place all the cows for all distances < x, i.e for search space <= x, our answer will be true. So we will be having one ans x. Now we will have to find maximum possible distance.

For example the given sample:-
5 3
1 2 8 4 9

Sort the array.

1 2 4 8 9
The search space will be 0 to 9
mid = 4.
Now place cow at 1, then at 8 because distance should be >= current mid(4).
The third cow cannot be placed now so for all values > 4, the result will be false and we will check the search space for mid - 1 = 3(clearing your doubt 3).

Now mid = 1
cow pos = 1, 2, 4.
Okay now for distance < 1, the search space will give true. So reducing search space from mid + 1(clearing your second doubt) to end, we will again repeat the process.

So dont see the code, try it yourself. You can do mid + 1 and mid - 1 as explained.

#3

Thankyou so much Kartik Sapra. I’ll definitely follow your advise and your hint worked as well. Thanks