Problem Description:
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
Explanation
B is of length 3 and it has all three one’s. There is no block of zeros, hence the output is 0.
Solution in C:
#include <stdio.h>
// Function to count zeros based on values of L and K
int zerocount(int L, int K) {
// Base case: if K is 0, return L
if (K == 0) {
return L;
}
// Base case: if K is equal to L, return 0
if (K == L) {
return 0;
}
// Initialize max_zeros to 0
int max_zeros = 0;
// If K is greater than 0, set max_zeros to 1
if (K > 0) {
max_zeros = 1;
}
// Return the value of max_zeros
return max_zeros;
}
int main() {
// Declare variables L and K
int L, K;
// Input values for L and K
scanf("%d %d", &L, &K);
// Call the zerocount function and store the result in res
int res = zerocount(L, K);
// Print the result
printf("%d\n", res);
return 0;
}
You can also run it on an online IDE:
https://ide.geeksforgeeks.org/online-c-compiler/17c95992-ebe1-4724-ae1f-ac10039b7fba
No comments:
Post a Comment