Count of 0 s to be flipped to make any two adjacent 1 s at least K 0 s apart | C ++ program for the above problem ; Function to find the count of 0 s to be flipped ; Loop traversal to mark K adjacent positions to the right of already existing 1 s . ; Loop traversal to mark K adjacent positions to the left of already existing 1 s . ; Loop to count the maximum number of 0 s that will be replaced by 1 s ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count ( int k , string s ) { int ar [ s . length ( ) ] ; int end = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( s [ i ] == '1' ) { for ( int j = i ; j < s . length ( ) && j <= i + k ; j ++ ) { ar [ j ] = -1 ; end = j ; } i = end ; } } end = 0 ; for ( int i = s . length ( ) - 1 ; i >= 0 ; i -- ) { if ( s [ i ] == '1' ) { for ( int j = i ; j >= 0 && j >= i - k ; j -- ) { ar [ j ] = -1 ; end = j ; } i = end ; } } int ans = 0 ; end = 0 ; for ( int j = 0 ; j < s . length ( ) ; j ++ ) { if ( ar [ j ] == 0 ) { ans ++ ; for ( int g = j ; g <= j + k && g < s . length ( ) ; g ++ ) { ar [ g ] = -1 ; end = g ; } j = end - 1 ; } } return ans ; } int main ( ) { int K = 2 ; string s = "000000" ; cout << count ( K , s ) << endl ; return 0 ; }