Queries to flip characters of a binary string in given range | Function to find the binary by performing all the given queries ; Stores length of the string ; prefixCnt [ i ] : Stores number of times strr [ i ] toggled by performing all the queries ; Update prefixCnt [ Q [ i ] [ 0 ] ] ; Update prefixCnt [ Q [ i ] [ 1 ] + 1 ] ; Calculate prefix sum of prefixCnt [ i ] ; Traverse prefixCnt [ ] array ; If ith element toggled odd number of times ; Toggled i - th element of binary string ; Driver Code
def toggleQuery ( strr , Q , M ) : NEW_LINE INDENT strr = [ i for i in strr ] NEW_LINE N = len ( strr ) NEW_LINE prefixCnt = [ 0 ] * ( N + 1 ) NEW_LINE for i in range ( M ) : NEW_LINE INDENT prefixCnt [ Q [ i ] [ 0 ] ] += 1 NEW_LINE prefixCnt [ Q [ i ] [ 1 ] + 1 ] -= 1 NEW_LINE DEDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT prefixCnt [ i ] += prefixCnt [ i - 1 ] NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT if ( prefixCnt [ i ] % 2 ) : NEW_LINE INDENT strr [ i ] = ( chr ( ord ( '1' ) - ord ( strr [ i ] ) + ord ( '0' ) ) ) NEW_LINE DEDENT DEDENT return " " . join ( strr ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT strr = "101010" ; NEW_LINE Q = [ [ 0 , 1 ] , [ 2 , 5 ] , [ 2 , 3 ] , [ 1 , 4 ] , [ 0 , 5 ] ] NEW_LINE M = len ( Q ) NEW_LINE print ( toggleQuery ( strr , Q , M ) ) NEW_LINE DEDENT