Minimum number of flips with rotation to make binary string alternating | Function that finds the minimum number of flips to make the binary string alternating if left circular rotation is allowed ; Initialize prefix arrays to store number of changes required to put 1 s at either even or odd position ; If i is odd ; Update the oddone and evenone count ; Else i is even ; Update the oddone and evenone count ; Initialize minimum flips ; Check if substring [ 0 , i ] is appended at end how many changes will be required ; Return minimum flips ; Given String ; Length of given string ; Function call
def MinimumFlips ( s , n ) : NEW_LINE INDENT a = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT a [ i ] = 1 if s [ i ] == '1' else 0 NEW_LINE DEDENT oddone = [ 0 ] * ( n + 1 ) NEW_LINE evenone = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( i % 2 != 0 ) : NEW_LINE INDENT if ( a [ i ] == 1 ) : NEW_LINE INDENT oddone [ i + 1 ] = oddone [ i ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT oddone [ i + 1 ] = oddone [ i ] + 0 NEW_LINE DEDENT if ( a [ i ] == 0 ) : NEW_LINE INDENT evenone [ i + 1 ] = evenone [ i ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT evenone [ i + 1 ] = evenone [ i ] + 0 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( a [ i ] == 0 ) : NEW_LINE INDENT oddone [ i + 1 ] = oddone [ i ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT oddone [ i + 1 ] = oddone [ i ] + 0 NEW_LINE DEDENT if ( a [ i ] == 1 ) : NEW_LINE INDENT evenone [ i + 1 ] = evenone [ i ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT evenone [ i + 1 ] = evenone [ i ] + 0 NEW_LINE DEDENT DEDENT DEDENT minimum = min ( oddone [ n ] , evenone [ n ] ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( n % 2 != 0 ) : NEW_LINE INDENT minimum = min ( minimum , oddone [ n ] - oddone [ i + 1 ] + evenone [ i + 1 ] ) NEW_LINE minimum = min ( minimum , evenone [ n ] - evenone [ i + 1 ] + oddone [ i + 1 ] ) NEW_LINE DEDENT DEDENT return minimum NEW_LINE DEDENT S = "000001100" NEW_LINE n = len ( S ) NEW_LINE print ( MinimumFlips ( S , n ) ) NEW_LINE