FunnyAlgorithms icon indicating copy to clipboard operation
FunnyAlgorithms copied to clipboard

Update AggressiveCows.cpp

Open SoulNikhar opened this issue 2 years ago • 0 comments

Here's the reason for returning l - 1:

  1. In a binary search, when the search ends (i.e., l > r), l will be the next possible candidate value for the answer. However, l may be too large, so you subtract 1 to get the largest distance smaller than l that satisfies the condition.

  2. The l value is always guaranteed to be a valid answer because it's the first value that doesn't satisfy the condition canPlace(stalls, k, mid) in the binary search loop. So, you subtract 1 from l to find the largest valid minimum distance.

In summary, returning l - 1 ensures that you correctly return the maximum possible minimum distance that allows you to place k cows in n stalls without violating the given condition. This is a common practice in binary search algorithms to find the largest valid value.

SoulNikhar avatar Oct 22 '23 19:10 SoulNikhar