Queries to flip characters of a binary string in given range
Given a binary string, str and a 2D array Q[][] representing queries of the form {L, R}. In each query, toggle all the characters of the binary strings present in the indices [L, R]. The task is to print the binary string by performing all the queries.
Examples:
Input: str = β101010β, Q[][] = { {0, 1}, {2, 5}, {2, 3}, {1, 4}, {0, 5} }
Output: 111000
Explanation:
Query 1: Toggling all the characters of str in the indices [0, 1]. Therefore, str becomes β011010β.
Query 2: Toggling all the characters of str in the indices [2, 5]. Therefore, str becomes β010101β.
Query 3: Toggling all the characters of str in the indices [2, 3]. Therefore, str becomes β011001β.
Query 4: Toggling all the characters of str in the indices [1, 4]. Therefore, str becomes β000111β.
Query 5: Toggling all the characters of str in the indices [0, 5]. Therefore, str becomes β111000β.
Therefore, the required binary string is β111000β.Input: str = β00101β, Q[][]={ {0, 2}, {2, 3}, {1, 4} }
Output: 10000
Naive Approach: The simplest approach to solve the problem is to traverse all the queries arrays and toggle all the characters in the indices [L, R]. Finally, print the binary string.
Time Complexity: O(M * N), Where N denotes the length of the binary string.
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is to use the Prefix Sum array technique. Follow the steps below to solve the problem:
- Initialize an array, say prefixCnt[] to store the value of the number of times ith element of the binary string toggled.
- Traverse the query Q[][] array and for each query, update the value of prefixCnt[Q[i][0]] += 1 and prefixCnt[Q[i][1] + 1] -= 1.
- Traverse the prefixCnt[] array and take the prefix sum of prefixCnt[] array.
- Finally, traverse the binary string and check if the value of prefixCnt[i] % 2 == 1 or not. If found to be true then toggled ith element of the binary string.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the binary string by // performing all the given queries string toggleQuery(string str, int Q[][2], int M) { // Stores length of the string int N = str.length(); // prefixCnt[i]: Stores number // of times str[i] toggled by // performing all the queries int prefixCnt[N + 1] = { 0 }; for ( int i = 0; i < M; i++) { // Update prefixCnt[Q[i][0]] prefixCnt[Q[i][0]] += 1; // Update prefixCnt[Q[i][1] + 1] prefixCnt[Q[i][1] + 1] -= 1; } // Calculate prefix sum of prefixCnt[i] for ( int i = 1; i <= N; i++) { prefixCnt[i] += prefixCnt[i - 1]; } // Traverse prefixCnt[] array for ( int i = 0; i < N; i++) { // If ith element toggled // odd number of times if (prefixCnt[i] % 2) { // Toggled i-th element // of binary string str[i] = '1' - str[i] + '0' ; } } return str; } // Driver Code 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); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the binary // String by performing all the // given queries static String toggleQuery( char [] str, int Q[][], int M) { // Stores length of the String int N = str.length; // prefixCnt[i]: Stores number // of times str[i] toggled by // performing all the queries int prefixCnt[] = new int [N + 1 ]; for ( int i = 0 ; i < M; i++) { // Update prefixCnt[Q[i][0]] prefixCnt[Q[i][ 0 ]] += 1 ; // Update prefixCnt[Q[i][1] + 1] prefixCnt[Q[i][ 1 ] + 1 ] -= 1 ; } // Calculate prefix sum of // prefixCnt[i] for ( int i = 1 ; i <= N; i++) { prefixCnt[i] += prefixCnt[i - 1 ]; } // Traverse prefixCnt[] array for ( int i = 0 ; i < N; i++) { // If ith element toggled // odd number of times if (prefixCnt[i] % 2 == 1 ) { // Toggled i-th element // of binary String str[i] = ( char )( '1' - str[i] + '0' ); } } return String.valueOf(str); } // Driver Code 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)); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program to implement # the above approach # Function to find the binary by # performing all the given queries def toggleQuery(strr, Q, M): strr = [i for i in strr] # Stores length of the string N = len (strr) # prefixCnt[i]: Stores number # of times strr[i] toggled by # performing all the queries prefixCnt = [ 0 ] * (N + 1 ) for i in range (M): # Update prefixCnt[Q[i][0]] prefixCnt[Q[i][ 0 ]] + = 1 # Update prefixCnt[Q[i][1] + 1] prefixCnt[Q[i][ 1 ] + 1 ] - = 1 # Calculate prefix sum of prefixCnt[i] for i in range ( 1 , N + 1 ): prefixCnt[i] + = prefixCnt[i - 1 ] # Traverse prefixCnt[] array for i in range (N): # If ith element toggled # odd number of times if (prefixCnt[i] % 2 ): # Toggled i-th element # of binary string strr[i] = ( chr ( ord ( '1' ) - ord (strr[i]) + ord ( '0' ))) return "".join(strr) # Driver Code if __name__ = = '__main__' : strr = "101010" ; Q = [ [ 0 , 1 ],[ 2 , 5 ], [ 2 , 3 ],[ 1 , 4 ], [ 0 , 5 ] ] M = len (Q) print (toggleQuery(strr, Q, M)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the binary // String by performing all the // given queries static String toggleQuery( char [] str, int [,]Q , int M) { // Stores length of the String int N = str.Length; // prefixCnt[i]: Stores number // of times str[i] toggled by // performing all the queries int []prefixCnt = new int [N + 1]; for ( int i = 0; i < M; i++) { // Update prefixCnt[Q[i,0]] prefixCnt[Q[i, 0]] += 1; // Update prefixCnt[Q[i,1] + 1] prefixCnt[Q[i, 1] + 1] -= 1; } // Calculate prefix sum of // prefixCnt[i] for ( int i = 1; i <= N; i++) { prefixCnt[i] += prefixCnt[i - 1]; } // Traverse prefixCnt[] array for ( int i = 0; i < N; i++) { // If ith element toggled // odd number of times if (prefixCnt[i] % 2 == 1) { // Toggled i-th element // of binary String str[i] = ( char )( '1' - str[i] + '0' ); } } return String.Join( "" , str); } // Driver Code public static void Main(String[] args) { String str = "101010" ; int [,]Q = {{0, 1}, {2, 5}, {2, 3}, {1, 4}, {0, 5}}; int M = Q.GetLength(0); Console.Write(toggleQuery(str.ToCharArray(), Q, M)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the binary // String by performing all the // given queries function toggleQuery(str, Q, M) { // Stores length of the String let N = str.length; // prefixCnt[i]: Stores number // of times str[i] toggled by // performing all the queries let prefixCnt = new Array(N + 1); for (let i = 0; i < N + 1; i++) { prefixCnt[i] = 0; } for (let i = 0; i < M; i++) { // Update prefixCnt[Q[i][0]] prefixCnt[Q[i][0]] += 1; // Update prefixCnt[Q[i][1] + 1] prefixCnt[Q[i][1] + 1] -= 1; } // Calculate prefix sum of // prefixCnt[i] for (let i = 1; i <= N; i++) { prefixCnt[i] += prefixCnt[i - 1]; } // Traverse prefixCnt[] array for (let i = 0; i < N; i++) { // If ith element toggled // odd number of times if (prefixCnt[i] % 2 == 1) { // Toggled i-th element // of binary String str[i] = String.fromCharCode( '1' .charCodeAt(0) - str[i].charCodeAt(0) + '0' .charCodeAt(0)); } } return (str).join( "" ); } // Driver Code let str = "101010" ; let Q = [[0, 1], [2, 5], [2, 3], [1, 4], [0, 5]]; let M = Q.length; document.write( toggleQuery(str.split( "" ), Q, M)); // This code is contributed by patel2127 </script> |
111000
Time Complexity: O(N + |Q|), Where N is the length of binary string.
Auxiliary Space: O(N)