Bitwise OR de Bitwise AND de todos los subconjuntos de un Array para consultas Q

Posted on by Rudeus Greyrat

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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *