How should i approach

#1

I am unable to solve this problem. How should i approach?

#2

@piyushabhiranjan30 Hi buddy, so lets develop the intuition of using binary search in this problem.

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.

Now this is the code for reference but before that i want you to write the code and dry run yourself buddy.

Also bro don’t forget to close the doubt by marking it resolved and rate full!
Happy coding!

1 Like
#3

Why we place cows at 1 and 8? as mid is 4 the distance between 1 and 4 is 3

#4

@piyushabhiranjan30 read the question carefully, we are given these pos only
1 2 8 4 9, now you placed first at 1 now distance should be >= current mid(4). so you cannot place at 2 now so next position which satisfies condn is 8, thats why we have done that sorted step.
Also dry run the code for custom input you will get it!