Consultas para calcular Bitwise OR de una array con actualizaciones

Dada una array arr[ ] que consta de N enteros positivos y una array 2D Q[][] que consta de consultas de la forma {i, val} , la tarea para cada consulta es reemplazar arr[i] por val y calcular Bitwise OR de la array modificada.

Ejemplos:

Entrada: arr[ ]= {1, 2, 3}, Q[ ][] = {{1, 4}, {3, 0}}
Salida: 7 6
Explicación:
Reemplazar arr[1] por 4 modifica arr[ ] a {4, 2, 3}. Bitwise OR = 7.
Reemplazar arr[2] por 0 modifica arr[] a {4, 2, 0}. OR bit a bit = 6.

Entrada: arr[ ]= {1, 2, 3, 4}, Q[][ ] = {{4, 0}, {2, 8}}
Salida: 3 11 
Explicación: 
Reemplazar arr[3] por 0 modifica arr [ ] a {1, 2, 3, 0}. Bitwise OR = 3.
Reemplazar arr[2] por 8 modifica arr[] a {1, 8, 3, 0}. OR bit a bit = 11.

Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array arr[ ] para cada i ^-ésima consulta después de actualizar arr[Q[i][0]] por Q[i][1] para calcular Bitwise OR  de la array . 

Complejidad de tiempo: O(N * sizeof(Q))
Espacio auxiliar: O(1)

Enfoque eficiente: siga los pasos a continuación para resolver el problema:

• Inicialice un resultado de array [] de tamaño 32. Establezca todos sus elementos en 0.
• Atraviesa la array arr[].
  • Iterar sobre los bits de cada elemento de la array.
  • Incremente el resultado[j] por cada j ^-ésimo bit no establecido que se encuentre en el elemento de array actual.

• Ahora, recorra la array Q[][] y realice lo siguiente:
  • Modifique result[] eliminando los bits establecidos de Q[i][0] de sus respectivas posiciones.
  • Actualice result[] agregando los bits establecidos de Q[i][0] desde sus respectivas posiciones.
  • Convierta la array result[] a su valor decimal equivalente e imprímala.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define bitsSize 32
 
// Function to convert a binary array
// to equivalent decimal representation
int toDecimal(int result[], int size)
{
    // Stores the decimal result
    int ans = 0;
 
    // Traverse the array
    for (int i = 0; i < size; i++) {
        // If non-zero element
        // is encountered
        if (result[i] != 0)
            ans += pow(2, i);
    }
 
    return ans;
}
 
// Function to replace an array
// element old_value by new_value
void findOrUtil(int result[],
                int old_value,
                int new_value)
{
    int i = 0;
 
    // Removing old value from result
    while (old_value != 0) {
        result[i] -= old_value % 2;
        old_value = old_value / 2;
        i++;
    }
 
    i = 0;
 
    // Adding new value to result
    while (new_value != 0) {
        result[i] += new_value % 2;
        new_value = new_value / 2;
        i++;
    }
}
 
// Function to calculate and print
// Bitwise OR of array for each query
void findOR(vector<int> arr,
            vector<pair<int, int> > queries)
{
    int result[bitsSize];
 
    // Initialize all bits to zero
    memset(result, 0, sizeof(result));
 
    // Precompute and fill result[]
    for (int i = 0; i < arr.size(); i++) {
        int val = arr[i];
        int j = 0;
 
        // Add all set bits to result[]
        while (val != 0) {
            result[j] += val % 2;
            val = val / 2;
            j++;
        }
    }
 
    // Traverse the queries
    for (int q = 0; q < queries.size(); q++) {
        int index = queries[q].first;
        int new_value = queries[q].second;
 
        // Update result[] by replacing
        // arr[index] by new_value
        findOrUtil(result, arr[index], new_value);
 
        // Modify arr[]
        arr[index] = new_value;
 
        // Calculate Bitwise OR
        int ans = toDecimal(result, bitsSize);
 
        // Print the value of Bitwise OR
        cout << ans << endl;
    }
}
 
// Driver Code
int main()
{
 
    // Given array
    vector<int> arr = { 1, 2, 3, 4 };
 
    // Queries of the form {i, value}
    vector<pair<int, int> > queries;
 
    // 0-indexed queries
    queries.push_back({ 3, 0 });
    queries.push_back({ 1, 8 });
 
    findOR(arr, queries);
 
    return 0;
}

// Java implementation of the approach
import java.util.ArrayList;
 
class GFG{
     
static int bitsSize = 32;
 
static class Pair{
     
    int first;
    int second;
     
    Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to convert a binary array
// to equivalent decimal representation
static int toDecimal(int result[], int size)
{
     
    // Stores the decimal result
    int ans = 0;
 
    // Traverse the array
    for(int i = 0; i < size; i++)
    {
         
        // If non-zero element
        // is encountered
        if (result[i] != 0)
            ans += Math.pow(2, i);
    }
    return ans;
}
 
// Function to replace an array
// element old_value by new_value
static void findOrUtil(int result[],
                       int old_value,
                       int new_value)
{
    int i = 0;
 
    // Removing old value from result
    while (old_value != 0)
    {
        result[i] -= old_value % 2;
        old_value = old_value / 2;
        i++;
    }
 
    i = 0;
 
    // Adding new value to result
    while (new_value != 0)
    {
        result[i] += new_value % 2;
        new_value = new_value / 2;
        i++;
    }
}
 
// Function to calculate and print
// Bitwise OR of array for each query
static void findOR(int[] arr, ArrayList<Pair> queries)
{
    int result[] = new int[bitsSize];
 
    // Precompute and fill result[]
    for(int i = 0; i < arr.length; i++)
    {
        int val = arr[i];
        int j = 0;
 
        // Add all set bits to result[]
        while (val != 0)
        {
            result[j] += val % 2;
            val = val / 2;
            j++;
        }
    }
 
    // Traverse the queries
    for(int q = 0; q < queries.size(); q++)
    {
        int index = queries.get(q).first;
        int new_value = queries.get(q).second;
 
        // Update result[] by replacing
        // arr[index] by new_value
        findOrUtil(result, arr[index], new_value);
 
        // Modify arr[]
        arr[index] = new_value;
 
        // Calculate Bitwise OR
        int ans = toDecimal(result, bitsSize);
 
        // Print the value of Bitwise OR
        System.out.println(ans);
    }
}
 
// Driver code
public static void main(String[] args)
{
 
    // Given array
    int arr[] = { 1, 2, 3, 4 };
 
    // Queries of the form {i, value}
    ArrayList<Pair> queries = new ArrayList<>();
 
    // 0-indexed queries
    queries.add(new Pair(3, 0));
    queries.add(new Pair(1, 8));
 
    findOR(arr, queries);
}
}
 
// This code is contributed by abhinavjain194

# Python3 implementation of the approach
 
# Function to convert a binary array
# to equivalent decimal representation
def toDecimal(result, size):
     
    # Stores the decimal result
    ans = 0
 
    # Traverse the array
    for i in range(size):
         
        # If non-zero element
        # is encountered
        if (result[i] != 0):
            ans += pow(2, i)
 
    return ans
 
# Function to replace an array
# element old_value by new_value
def findOrUtil(result, old_value, new_value):
     
    i = 0
 
    # Removing old value from result
    while (old_value != 0):
        result[i] -= old_value % 2
        old_value = old_value // 2
        i += 1
 
    i = 0
 
    # Adding new value to result
    while (new_value != 0):
        result[i] += new_value % 2
        new_value = new_value // 2
        i += 1
 
# Function to calculate and print
# Bitwise OR of array for each query
def findOR(arr, queries):
     
    result = [0] * 32
 
    # Initialize all bits to zero
    # memset(result, 0, sizeof(result))
 
    # Precompute and fill result[]
    for i in range(len(arr)):
        val = arr[i]
        j = 0
 
        # Add all set bits to result[]
        while (val != 0):
            result[j] += val % 2
            val = val // 2
            j += 1
 
    # Traverse the queries
    for q in range(len(queries)):
        index = queries[q][0]
        new_value = queries[q][1]
 
        # Update result[] by replacing
        # arr[index] by new_value
        findOrUtil(result, arr[index],
                   new_value)
 
        # Modify arr[]
        arr[index] = new_value
 
        # Calculate Bitwise OR
        ans = toDecimal(result, 32)
 
        # Print the value of Bitwise OR
        print (ans)
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    arr = [ 1, 2, 3, 4 ]
 
    # Queries of the form {i, value}
    queries = []
 
    # 0-indexed queries
    queries.append([3, 0])
    queries.append([1, 8])
 
    findOR(arr, queries)
 
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG{
     
static int bitsSize = 32;
 
class Pair{
     
    public int first;
    public int second;
     
    public Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to convert a binary array
// to equivalent decimal representation
static int toDecimal(int []result, int size)
{
     
    // Stores the decimal result
    int ans = 0;
 
    // Traverse the array
    for(int i = 0; i < size; i++)
    {
         
        // If non-zero element
        // is encountered
        if (result[i] != 0)
            ans += (int)Math.Pow(2, i);
    }
    return ans;
}
 
// Function to replace an array
// element old_value by new_value
static void findOrUtil(int []result,
                       int old_value,
                       int new_value)
{
    int i = 0;
 
    // Removing old value from result
    while (old_value != 0)
    {
        result[i] -= old_value % 2;
        old_value = old_value / 2;
        i++;
    }
    i = 0;
 
    // Adding new value to result
    while (new_value != 0)
    {
        result[i] += new_value % 2;
        new_value = new_value / 2;
        i++;
    }
}
 
// Function to calculate and print
// Bitwise OR of array for each query
static void findOR(int[] arr, List<Pair> queries)
{
    int []result = new int[bitsSize];
 
    // Precompute and fill result[]
    for(int i = 0; i < arr.Length; i++)
    {
        int val = arr[i];
        int j = 0;
 
        // Add all set bits to result[]
        while (val != 0)
        {
            result[j] += val % 2;
            val = val / 2;
            j++;
        }
    }
 
    // Traverse the queries
    for(int q = 0; q < queries.Count; q++)
    {
        int index = queries[q].first;
        int new_value = queries[q].second;
 
        // Update result[] by replacing
        // arr[index] by new_value
        findOrUtil(result, arr[index], new_value);
 
        // Modify []arr
        arr[index] = new_value;
 
        // Calculate Bitwise OR
        int ans = toDecimal(result, bitsSize);
 
        // Print the value of Bitwise OR
        Console.WriteLine(ans);
    }
}
 
// Driver code
public static void Main(String[] args)
{
 
    // Given array
    int []arr = { 1, 2, 3, 4 };
 
    // Queries of the form {i, value}
    List<Pair> queries = new List<Pair>();
 
    // 0-indexed queries
    queries.Add(new Pair(3, 0));
    queries.Add(new Pair(1, 8));
 
    findOR(arr, queries);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation of the approach
var bitsSize = 32;
 
// Function to convert a binary array
// to equivalent decimal representation
function toDecimal(result, size)
{
    // Stores the decimal result
    var ans = 0;
    var i;
    // Traverse the array
    for (i = 0; i < size; i++) {
        // If non-zero element
        // is encountered
        if (result[i] != 0)
            ans += Math.pow(2, i);
    }
 
    return ans;
}
 
// Function to replace an array
// element old_value by new_value
function findOrUtil(result, old_value, new_value)
{
    var i = 0;
 
    // Removing old value from result
    while (old_value != 0) {
        result[i] -= old_value % 2;
        old_value = parseInt(old_value / 2);
        i++;
    }
 
    i = 0;
 
    // Adding new value to result
    while(new_value != 0) {
        result[i] += new_value % 2;
        new_value = parseInt(new_value / 2);
        i++;
    }
}
 
// Function to calculate and print
// Bitwise OR of array for each query
function findOR(arr, queries)
{
    var result = Array(bitsSize).fill(0);
      
    var i;
    // Precompute and fill result[]
    for (i = 0; i < arr.length; i++) {
        var val = arr[i];
        var j = 0;
 
        // Add all set bits to result[]
        while (val != 0) {
            result[j] += val % 2;
            val = parseInt(val / 2);
            j++;
        }
    }
     
    var q;
    // Traverse the queries
    for (q = 0; q < queries.length; q++) {
        var index = queries[q][0];
        var new_value = queries[q][1];
 
        // Update result[] by replacing
        // arr[index] by new_value
        findOrUtil(result, arr[index], new_value);
 
        // Modify arr[]
        arr[index] = new_value;
 
        // Calculate Bitwise OR
        var ans = toDecimal(result, bitsSize);
 
        // Print the value of Bitwise OR
        document.write(ans+"<br>");
    }
}
 
// Driver Code
 
    // Given array
    var arr = [1, 2, 3, 4];
 
    // Queries of the form {i, value}
    var queries = [[3, 0],[1, 8]]
 
    findOR(arr, queries);
 
</script>

3
11

Complejidad temporal : O(N)
Espacio auxiliar: O(1)