Aggressive Cow problem

#1

Please explain this question . because I don’t understand

#2

I don’t get logic and not understand

#3

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

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 to end, we will again repeat the process.

So this is what question is, its good question so i want you to try yourself first after reading this approach!

Happy coding!