Question

You are given a binary string B of length L which contains K ones and remaining zeros. You are required to place the K ones in the binary string in such a way that the longest consecutive zeros have the least length possible. Once such a binary string is constructed, you are required to print the length of the contiguous block of zeros, which has the largest length.Constraints

0 <= K <= L
1 <= L <= 10^6
Input

Single line consisting of two space separated integers denoting L and K.
Output

Print a single integer denoting the length of the longest consecutive zeros as per the problem.Time Limit (secs)
1
Examples
Example 1
Input
3 1
Output
1
Explanation
B is of length 3 and it has 1 one's.

So the possible strings as per the problem are 010, 001, 100.

In the first case, the maximum length of consecutive zeros is 1 whereas in the other two cases it is 2. Hence the constructed binary string is 010 and the output is 1.

Example 2

Input
3 3
Output

0

Answer 1

Place ones as far apart as possible to minimize consecutive zeros.

To minimize the length of the longest consecutive zeros in a binary string with K ones, place the K ones as far apart as possible. This can be achieved by placing the first one at the beginning of the string, the second one at the kth position from the end of the string, the third one at the 2kth position from the end, and so on. This will ensure that the zeros in between the ones are as far apart as possible, minimizing the length of the longest consecutive zeros.

Here's the algorithm to determine the length of the longest consecutive zeros:

1. Initialize the 'longestZeros' variable to 0.

2. Iterate through the binary string, starting from the end.

3. If the current character is '1', update the 'longestZeros' variable with the current index. This is because the current position is the beginning of a new block of zeros.

4. Return the value of the 'longestZeros' variable.