Minimum shifts of substrings of 1 s required to group all 1 s together in a given Binary string | C ++ program for the above approach ; Function to count indices substrings of 1 s need to be shifted such that all 1 s in the string are grouped together ; Stores first occurrence of '1' ; Stores last occurrence of '1' ; Count of 0 s between firstOne and lastOne ; Traverse the string to find the first and last occurrences of '1' ; Count number of 0 s present between firstOne and lastOne ; Print minimum operations ; Driver Code ; Given string
#include <bits/stdc++.h> NEW_LINE using namespace std ; void countShifts ( string str ) { int firstOne = -1 ; int lastOne = -1 ; int count = 0 ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { if ( str [ i ] == '1' ) { if ( firstOne == -1 ) firstOne = i ; lastOne = i ; } } if ( ( firstOne == -1 ) || ( firstOne == lastOne ) ) { cout << 0 ; return ; } for ( int i = firstOne ; i <= lastOne ; i ++ ) { if ( str [ i ] == '0' ) { count ++ ; } } cout << count << endl ; } int main ( ) { string str = "00110111011" ; countShifts ( str ) ; return 0 ; }