Dada una string binaria , str y una array 2D Q[][] que representan consultas de la forma {L, R} . En cada consulta, alterne todos los caracteres de las strings binarias presentes en los índices [L, R] . La tarea es imprimir la string binaria realizando todas las consultas.
Ejemplos:
Entrada: str = “101010”, Q[][] = { {0, 1}, {2, 5}, {2, 3}, {1, 4}, {0, 5} }
Salida: 111000
Explicación:
Consulta 1: Alternar todos los caracteres de str en los índices [0, 1]. Por lo tanto, str se convierte en «011010».
Consulta 2: Alternar todos los caracteres de str en los índices [2, 5]. Por lo tanto, str se convierte en «010101».
Consulta 3: Alternar todos los caracteres de str en los índices [2, 3]. Por lo tanto, str se convierte en «011001».
Consulta 4: Alternar todos los caracteres de str en los índices [1, 4]. Por lo tanto, str se convierte en «000111».
Consulta 5: Alternar todos los caracteres de str en los índices [0, 5]. Por lo tanto, str se convierte en “111000”.
Por lo tanto, la string binaria requerida es «111000».Entrada: str = “00101”, Q[][]={ {0, 2}, {2, 3}, {1, 4} }
Salida: 10000
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer todas las arrays de consultas y alternar todos los caracteres en los índices [L, R] . Finalmente, imprima la string binaria.
Complejidad de tiempo: O(M * N), donde N denota la longitud de la string binaria .
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la técnica de array Prefix Sum . Siga los pasos a continuación para resolver el problema:
- Inicialice una array, diga prefixCnt[] para almacenar el valor de la cantidad de veces que se alteró el i -ésimo elemento de la string binaria.
- Recorra la array de consulta Q[][] y para cada consulta, actualice el valor de prefixCnt[Q[i][0]] += 1 y prefixCnt[Q[i][1] + 1] -= 1 .
- Atraviese la array prefixCnt[] y tome la suma del prefijo de la array prefixCnt[] .
- Finalmente, recorra la string binaria y verifique si el valor de prefixCnt[i] % 2 == 1 o no. Si se determina que es cierto, entonces alterna el i -ésimo elemento de la string binaria.
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de tiempo: O(N + |Q|), donde N es la longitud de la string binaria.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aaryaverma112 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA