Check if any pair of consecutive 1 s can be separated by at most M 0 s by circular rotation of a Binary String | C ++ program for the above approach ; Function to check if any pair of consecutive 1 s can be separated by at most M 0 s by circular rotation of string S ; Stores the indices of all 1 s ; Store the number of pairs separated by at least M 0 s ; Traverse the string ; Store the current index ; Traverse the array containing indices ; If the number of 0 s > M , then increment cnt by 1 ; Increment cnt ; Check if at least M '0' s lie between the first and last occurrence of '1' ; Increment cnt ; If the value of cnt <= 1 , then rotation of string is possible ; Otherwise ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void rotateString ( int n , int m , string s ) { vector < int > v ; int cnt = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( s [ i ] == '1' ) { v . push_back ( i ) ; } } for ( int i = 1 ; i < ( int ) v . size ( ) ; i ++ ) { if ( ( v [ i ] - v [ i - 1 ] - 1 ) > m ) { cnt ++ ; } } if ( v . size ( ) >= 2 && ( n - ( v . back ( ) - v [ 0 ] ) - 1 ) > m ) { cnt ++ ; } if ( cnt <= 1 ) { cout << " Yes " ; } else { cout << " No " ; } } int main ( ) { string S = "101001" ; int M = 1 ; int N = S . size ( ) ; rotateString ( N , M , S ) ; return 0 ; }