Queries to flip characters of a binary string in given range | Function to find the binary String by performing all the given queries ; Stores length of the String ; prefixCnt [ i ] : Stores number of times str [ 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
function toggleQuery ( str , Q , M ) { let N = str . length ; let prefixCnt = new Array ( N + 1 ) ; for ( let i = 0 ; i < N + 1 ; i ++ ) { prefixCnt [ i ] = 0 ; } for ( let i = 0 ; i < M ; i ++ ) { prefixCnt [ Q [ i ] [ 0 ] ] += 1 ; prefixCnt [ Q [ i ] [ 1 ] + 1 ] -= 1 ; } for ( let i = 1 ; i <= N ; i ++ ) { prefixCnt [ i ] += prefixCnt [ i - 1 ] ; } for ( let i = 0 ; i < N ; i ++ ) { if ( prefixCnt [ i ] % 2 == 1 ) { str [ i ] = String . fromCharCode ( ' ' . charCodeAt ( 0 ) - str [ i ] . charCodeAt ( 0 ) + ' ' . charCodeAt ( 0 ) ) ; } } return ( str ) . join ( " " ) ; } let str = " " ; let Q = [ [ 0 , 1 ] , [ 2 , 5 ] , [ 2 , 3 ] , [ 1 , 4 ] , [ 0 , 5 ] ] ; let M = Q . length ; document . write ( toggleQuery ( str . split ( " " ) , Q , M ) ) ;