Queries to flip characters of a binary string in given range | C ++ program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; string toggleQuery ( string str , int Q [ ] [ 2 ] , int M ) { int N = str . length ( ) ; int prefixCnt [ N + 1 ] = { 0 } ; for ( int i = 0 ; i < M ; i ++ ) { prefixCnt [ Q [ i ] [ 0 ] ] += 1 ; prefixCnt [ Q [ i ] [ 1 ] + 1 ] -= 1 ; } for ( int i = 1 ; i <= N ; i ++ ) { prefixCnt [ i ] += prefixCnt [ i - 1 ] ; } for ( int i = 0 ; i < N ; i ++ ) { if ( prefixCnt [ i ] % 2 ) { str [ i ] = '1' - str [ i ] + '0' ; } } return str ; } int main ( ) { string str = "101010" ; int Q [ ] [ 2 ] = { { 0 , 1 } , { 2 , 5 } , { 2 , 3 } , { 1 , 4 } , { 0 , 5 } } ; int M = sizeof ( Q ) / sizeof ( Q [ 0 ] ) ; cout << toggleQuery ( str , Q , M ) ; }