Queries to flip characters of a binary string in given range | Java 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
import java . util . * ; class GFG { static String toggleQuery ( char [ ] str , int Q [ ] [ ] , int M ) { int N = str . length ; int prefixCnt [ ] = new int [ N + 1 ] ; 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 == 1 ) { str [ i ] = ( char ) ( '1' - str [ i ] + '0' ) ; } } return String . valueOf ( str ) ; } public static void main ( String [ ] args ) { String str = "101010" ; int Q [ ] [ ] = { { 0 , 1 } , { 2 , 5 } , { 2 , 3 } , { 1 , 4 } , { 0 , 5 } } ; int M = Q . length ; System . out . print ( toggleQuery ( str . toCharArray ( ) , Q , M ) ) ; } }