Minimum prefixes required to be flipped to convert a Binary String to another | C ++ program for the above approach ; Function to count flips required to make strings A and B equal ; Stores the count of the number of operations ; Stores the length of the chosen prefixes ; Stores if operations are performed even or odd times ; Traverse the given string ; If current characters in the two strings are unequal ; If A [ i ] is not flipped ; Increment count of operations ; Insert the length of the chosen prefix ; Update invert to true ; If A [ i ] is flipped ; Increment count of operations ; Insert length of the chosen prefix ; Update invert to false ; Print the number of operations required ; Print the chosen prefix length in each operation ; Driver Code ; Given binary strings
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findOperations ( string A , string B , int N ) { int operations = 0 ; vector < int > ops ; bool invert = false ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( A [ i ] != B [ i ] ) { if ( ! invert ) { operations ++ ; ops . push_back ( i + 1 ) ; invert = true ; } } else { if ( invert ) { operations ++ ; ops . push_back ( i + 1 ) ; invert = false ; } } } cout << operations << endl ; if ( operations != 0 ) { for ( auto x : ops ) cout << x << " ▁ " ; } } int main ( ) { string A = "001" , B = "000" ; int N = A . size ( ) ; findOperations ( A , B , N ) ; return 0 ; }