Dadas dos arrays arr[] de tamaño N y queries[] de tamaño Q, la tarea es encontrar el OR de AND de subconjuntos de la array . En cada consulta, se le da un índice y un valor, debe reemplazar el valor en el índice dado de las arrays con un valor dado e imprimir el OR de AND de todos los subconjuntos de la array después de cada consulta.
Ejemplos:
Entrada: arr[] = {3, 5, 7}, N = 3, queries[] = {{1, 2}, {2, 1}}, Q = 2
Salida: 7
3
Explicación:
Para la primera consulta , reemplace el valor en el índice 1 con el valor 2, la array actualizada arr[] es {3, 2, 7}.
Luego tome AND de todos los subconjuntos, es decir, AND(3) = 3, AND(2) = 2, AND(7) = 7, AND(3, 2) = 2, AND(3, 7) = 3, AND(3, 2, 7) = 2.
OR de AND de todos los subconjuntos son OR(3, 2, 7, 2, 3, 2) = 7.
Ahora, para la segunda consulta , reemplace el valor en el índice 2 con el valor 1, array actualizada arr[] es {3, 2, 1}.
Luego tome AND de todos los subconjuntos, es decir, AND(3) = 3, AND(2) = 2, AND(1) = 1, AND(3, 2) = 2, AND(3, 1) = 1, AND(3, 2, 1) = 0.
OR del AND de todos los subconjuntos OR(3, 2, 1, 2, 1, 0) = 3.Entrada: arr[] = {1, 2, 3}, N = 3, consultas[] = {{2, 4}, {1, 8}}, Q = 2
Salida: 7
13
Enfoque: Este problema se puede resolver usando un algoritmo codicioso . Siga los pasos a continuación para resolver el problema:
- Inicialice una array de bits [] de tamaño 32 y almacene el recuento de bits establecidos de todos los elementos.
- Iterar en el rango [0, Q-1] usando la variable p :
- Primero reste los bits del valor anterior y luego agregue los bits del nuevo valor.
- Iterar en el rango [0, 31] usando la variable i :
- Si el bit actual está configurado para el valor anterior, entonces reste un bit a la array bits[] en el i-ésimo índice.
- Si el bit actual está configurado para el nuevo valor, entonces agregue un bit a la array bits[] en el i-ésimo índice.
- Reemplace el nuevo valor del valor anterior en la array dada arr[].
- Inicialice una variable y almacene el OR de la array de bits .
- Iterar en el rango [0, 31] usando la variable i :
- Si el bit actual no es igual a 0, agregue el OR del bit actual en ans .
- Después de completar los pasos anteriores, imprima la respuesta como la respuesta requerida para cada consulta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the OR of AND of all // subsets of the array for each query void Or_of_Ands_for_each_query(int arr[], int n, int queries[][2], int q) { // An array to store the bits int bits[32] = { 0 }; // Iterate for all the bits for (int i = 0; i < 32; i++) { // Iterate over all the numbers and // store the bits in bits[] array for (int j = 0; j < n; j++) { if ((1 << i) & arr[j]) { bits[i]++; } } } // Iterate over all the queries for (int p = 0; p < q; p++) { // Replace the bits of the value // at arr[queries[p][0]] with the bits // of queries[p][1] for (int i = 0; i < 32; i++) { if ((1 << i) & arr[queries[p][0]]) { bits[i]--; } if (queries[p][1] & (1 << i)) { bits[i]++; } } // Substitute the value in the array arr[queries[p][0]] = queries[p][1]; int ans = 0; // Find OR of the bits[] array for (int i = 0; i < 32; i++) { if (bits[i] != 0) { ans |= (1 << i); } } // Print the answer cout << ans << endl; } } // Driver Code int main() { // Given Input int n = 3, q = 2; int arr[] = { 3, 5, 7 }; int queries[2][2] = { { 1, 2 }, { 2, 1 } }; // Function Call Or_of_Ands_for_each_query(arr, n, queries, q); return 0; }
Java
// java program for the above approach import java.util.*; class GFG { // Function to find the OR of AND of all // subsets of the array for each query static void Or_of_Ands_for_each_query(int arr[], int n, int queries[][], int q) { // An array to store the bits int bits[] = new int[32]; Arrays.fill(bits, 0); // Iterate for all the bits for (int i = 0; i < 32; i++) { // Iterate over all the numbers and // store the bits in bits[] array for (int j = 0; j < n; j++) { if (((1 << i) & arr[j]) != 0) { bits[i]++; } } } // Iterate over all the queries for (int p = 0; p < q; p++) { // Replace the bits of the value // at arr[queries[p][0]] with the bits // of queries[p][1] for (int i = 0; i < 32; i++) { if (((1 << i) & arr[queries[p][0]]) != 0) { bits[i]--; } if ((queries[p][1] & (1 << i)) != 0) { bits[i]++; } } // Substitute the value in the array arr[queries[p][0]] = queries[p][1]; int ans = 0; // Find OR of the bits[] array for (int i = 0; i < 32; i++) { if (bits[i] != 0) { ans |= (1 << i); } } // Print the answer System.out.println(ans); } } // Driver Code public static void main(String[] args) { // Given Input int n = 3, q = 2; int arr[] = { 3, 5, 7 }; int queries[][] = { { 1, 2 }, { 2, 1 } }; // Function Call Or_of_Ands_for_each_query(arr, n, queries, q); } } // This code is contributed by subhammahato348.
Python3
# Python3 program for the above approach # Function to find the OR of AND of all # subsets of the array for each query def Or_of_Ands_for_each_query(arr, n, queries, q): # An array to store the bits bits = [0 for x in range(32)] # Iterate for all the bits for i in range(0, 32): # Iterate over all the numbers and # store the bits in bits[] array for j in range(0, n): if ((1 << i) & arr[j]): bits[i] += 1 # Iterate over all the queries for p in range(0, q): # Replace the bits of the value # at arr[queries[p][0]] with the bits # of queries[p][1] for i in range(0, 32): if ((1 << i) & arr[queries[p][0]]): bits[i] -= 1 if (queries[p][1] & (1 << i)): bits[i] += 1 # Substitute the value in the array arr[queries[p][0]] = queries[p][1] ans = 0 # Find OR of the bits[] array for i in range(0, 32): if (bits[i] != 0): ans |= (1 << i) # Print the answer print(ans) # Driver Code # Given Input n = 3 q = 2 arr = [3, 5, 7] queries = [[1, 2], [2, 1]] # Function Call Or_of_Ands_for_each_query(arr, n, queries, q) # This code is contributed by amreshkumar3
C#
// C# program for the above approach using System; class GFG{ // Function to find the OR of AND of all // subsets of the array for each query static void Or_of_Ands_for_each_query(int[] arr, int n, int[,] queries, int q) { // An array to store the bits int[] bits = new int[32]; for(int i = 0; i < 32; i++) { bits[i] = 0; } // Iterate for all the bits for(int i = 0; i < 32; i++) { // Iterate over all the numbers and // store the bits in bits[] array for(int j = 0; j < n; j++) { if (((1 << i) & arr[j]) != 0) { bits[i]++; } } } // Iterate over all the queries for(int p = 0; p < q; p++) { // Replace the bits of the value // at arr[queries[p][0]] with the bits // of queries[p][1] for(int i = 0; i < 32; i++) { if (((1 << i) & arr[queries[p, 0]]) != 0) { bits[i]--; } if ((queries[p, 1] & (1 << i)) != 0) { bits[i]++; } } // Substitute the value in the array arr[queries[p, 0]] = queries[p, 1]; int ans = 0; // Find OR of the bits[] array for(int i = 0; i < 32; i++) { if (bits[i] != 0) { ans |= (1 << i); } } // Print the answer Console.WriteLine(ans); } } // Driver Code public static void Main(String[] args) { // Given Input int n = 3, q = 2; int[] arr = { 3, 5, 7 }; int[,] queries = { { 1, 2 }, { 2, 1 } }; // Function Call Or_of_Ands_for_each_query(arr, n, queries, q); } } // This code is contributed by target_2
Javascript
<script> // JavaScript program for the above approach // Function to find the OR of AND of all // subsets of the array for each query function Or_of_Ands_for_each_query(arr, n, queries, q) { // An array to store the bits let bits = new Array(32).fill(0); // Iterate for all the bits for (let i = 0; i < 32; i++) { // Iterate over all the numbers and // store the bits in bits[] array for (let j = 0; j < n; j++) { if ((1 << i) & arr[j]) { bits[i]++; } } } // Iterate over all the queries for (let p = 0; p < q; p++) { // Replace the bits of the value // at arr[queries[p][0]] with the bits // of queries[p][1] for (let i = 0; i < 32; i++) { if ((1 << i) & arr[queries[p][0]]) { bits[i]--; } if (queries[p][1] & (1 << i)) { bits[i]++; } } // Substitute the value in the array arr[queries[p][0]] = queries[p][1]; let ans = 0; // Find OR of the bits[] array for (let i = 0; i < 32; i++) { if (bits[i] != 0) { ans |= (1 << i); } } // Print the answer document.write(ans + "<br>"); } } // Driver Code // Given Input let n = 3, q = 2; let arr = [3, 5, 7]; let queries = [[1, 2], [2, 1]]; // Function Call Or_of_Ands_for_each_query(arr, n, queries, q); // This code is contributed by Potta Lokesh </script>
7 3
Complejidad de tiempo: O(max(N, Q))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shrayansh95 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA