Consultas para actualizar cada elemento en el subarreglo a Bitwise XOR con un valor dado

Posted on by Rudeus Greyrat

Dada una array arr[] y consultas Q[][] de la forma (l, r, val) , la tarea de cada consulta es actualizar todos los elementos en los índices [l – 1, r – 1] a Bitwise XOR con val . Imprima la array final obtenida después de completar todas las consultas.
Ejemplos: 
 

Entrada : arr[] = {2, 3, 6, 5, 4}, Q[][] = {{1, 3, 2}, {2, 4, 4}} 
Salida: 0 5 0 1 4 
Explicación: 
1.ª consulta: el subarreglo en cuestión {2, 3, 6} se modifica a {0, 1, 4} después de reemplazar cada elemento con su XOR con val(= 2) 
El arreglo modificado es {0, 1, 4, 5, 4}  Segunda
consulta: el subarreglo en cuestión {1, 4, 5} se modifica a {5, 0, 1} después de reemplazar cada elemento con su XOR con val (= 4)  Por lo tanto, el arreglo final es {0, 5, 0, 1, 4} Entrada: arr[] = {1, 3, 5}, Q[][] = {{1, 2, 8}, {2, 3, 3}}  Salida: 9 8 6 



 

Enfoque ingenuo: 
el enfoque más simple para resolver este problema es recorrer los índices [l – 1, r – 1] para cada consulta y reemplazar arr[i] por arr[i]^val . Después de completar todas las consultas, imprima la array modificada. 
Complejidad de tiempo: O(N*sizeof(Q)) 
Espacio auxiliar: O(1)
Enfoque: Siga los pasos para resolver el problema procesando cada consulta en una complejidad de tiempo constante: 
 

  • Inicialice una array temp[] con todos ceros.
  • Para cada consulta de la forma (l, r, val) , actualice temp[l – 1] y temp[r] con su respectivo XOR con val .
  • Después de completar el paso anterior para cada consulta, convierta temp[] en una array XOR de prefijo .
  • Finalmente, realice la actualización arr[] reemplazando cada i -ésimo elemento con su XOR .

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 perform XOR in
// the range [lo, hi]
void findxor(int temp[], int N,
             int lo, int hi, int val)
{
    temp[lo] ^= val;
    if (hi != N - 1)
        temp[hi + 1] ^= val;
}
 
// Function to generate Prefix
// Xor Array
void updateArray(int temp[], int N)
{
    for (int i = 1; i < N; i++)
        temp[i] ^= temp[i - 1];
}
 
// Function to perform each Query
// and print the final array
void xorQuery(int arr[], int n,
              vector<vector<int> > Q)
{
 
    int temp[n];
    // initialize temp array to 0
    memset(temp, 0, sizeof(temp));
 
    // Perform each Query
    for (int i = 0; i < Q.size(); i++) {
        findxor(temp, n, Q[i][0] - 1,
                Q[i][1] - 1, Q[i][2]);
    }
 
    // Modify the array
    updateArray(temp, n);
 
    // Print the final array
    for (int i = 0; i < n; ++i) {
        cout << (arr[i] ^ temp[i]) << " ";
    }
}
 
// Driver Code
int main()
{
 
    int arr[] = { 2, 3, 6, 5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    vector<vector<int> > Q = { { 1, 3, 2 },
                               { 2, 4, 4 } };
 
    xorQuery(arr, n, Q);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function to perform XOR in
// the range [lo, hi]
static void findxor(int temp[], int N,
                    int lo, int hi, int val)
{
    temp[lo] ^= val;
    if (hi != N - 1)
        temp[hi + 1] ^= val;
}
 
// Function to generate Prefix
// Xor Array
static void updateArray(int temp[], int N)
{
    for(int i = 1; i < N; i++)
        temp[i] ^= temp[i - 1];
}
 
// Function to perform each Query
// and print the final array
static void xorQuery(int arr[], int n,
                     int[][] Q)
{
    int[] temp = new int[n];
 
    // Perform each Query
    for(int i = 0; i < Q.length; i++)
    {
        findxor(temp, n, Q[i][0] - 1,
                         Q[i][1] - 1,
                         Q[i][2]);
    }
 
    // Modify the array
    updateArray(temp, n);
 
    // Print the final array
    for(int i = 0; i < n; ++i)
    {
        System.out.print((arr[i] ^ temp[i]) + " ");
    }
}
 
// Driver Code
public static void main (String[] args)
{
    int arr[] = { 2, 3, 6, 5, 4 };
    int n = arr.length;
     
    int[][] Q = { { 1, 3, 2 },
                  { 2, 4, 4 } };
     
    xorQuery(arr, n, Q);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program to implement
# the above approach
 
# Function to perform XOR in
# the range [lo, hi]
def findxor(temp, N, lo, hi, val):
 
    temp[lo] ^= val
    if (hi != N - 1):
        temp[hi + 1] ^= val
 
# Function to generate Prefix
# Xor Array
def updateArray(temp, N):
 
    for i in range(1, N):
        temp[i] ^= temp[i - 1]
 
# Function to perform each Query
# and print the final array
def xorQuery(arr, n, Q):
 
    temp =[0] * n
 
    # Perform each Query
    for i in range(len(Q)):
        findxor(temp, n, Q[i][0] - 1,
                         Q[i][1] - 1,
                         Q[i][2])
 
    # Modify the array
    updateArray(temp, n)
 
    # Print the final array
    for i in range(n):
        print((arr[i] ^ temp[i]), end = " ")
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 2, 3, 6, 5, 4 ]
    n = len(arr)
    Q = [ [ 1, 3, 2 ],
          [ 2, 4, 4 ] ]
 
    xorQuery(arr, n, Q)
 
# This code is contributed by chitranayal

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to perform XOR in
// the range [lo, hi]
static void findxor(int []temp, int N,
                    int lo, int hi, int val)
{
    temp[lo] ^= val;
     
    if (hi != N - 1)
        temp[hi + 1] ^= val;
}
 
// Function to generate Prefix
// Xor Array
static void updateArray(int []temp, int N)
{
    for(int i = 1; i < N; i++)
        temp[i] ^= temp[i - 1];
}
 
// Function to perform each Query
// and print the readonly array
static void xorQuery(int []arr, int n,
                     int[,] Q)
{
    int[] temp = new int[n];
 
    // Perform each Query
    for(int i = 0; i < Q.GetLength(0); i++)
    {
        findxor(temp, n, Q[i, 0] - 1,
                         Q[i, 1] - 1,
                         Q[i, 2]);
    }
 
    // Modify the array
    updateArray(temp, n);
 
    // Print the readonly array
    for(int i = 0; i < n; ++i)
    {
        Console.Write((arr[i] ^ temp[i]) + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 2, 3, 6, 5, 4 };
    int n = arr.Length;
     
    int[,] Q = { { 1, 3, 2 },
                 { 2, 4, 4 } };
     
    xorQuery(arr, n, Q);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript Program to implement
// the above approach
 
// Function to perform XOR in
// the range [lo, hi]
function findxor(temp, N, lo, hi, val) {
    temp[lo] ^= val;
    if (hi != N - 1)
        temp[hi + 1] ^= val;
}
 
// Function to generate Prefix
// Xor Array
function updateArray(temp, N) {
    for (let i = 1; i < N; i++)
        temp[i] ^= temp[i - 1];
}
 
// Function to perform each Query
// and print the final array
function xorQuery(arr, n, Q) {
 
    let temp = new Array(n);
    // initialize temp array to 0
    temp.fill(0)
 
    // Perform each Query
    for (let i = 0; i < Q.length; i++) {
        findxor(temp, n, Q[i][0] - 1,
            Q[i][1] - 1, Q[i][2]);
    }
 
    // Modify the array
    updateArray(temp, n);
 
    // Print the final array
    for (let i = 0; i < n; ++i) {
        document.write(`${arr[i] ^ temp[i]} `);
    }
}
 
// Driver Code
 
let arr = [2, 3, 6, 5, 4];
let n = arr.length;
let Q = [[1, 3, 2],
[2, 4, 4]];
 
xorQuery(arr, n, Q);
 
// This code is contributed by gfgking
</script>
Producción: 

0 5 0 1 4

 

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

Publicación traducida automáticamente

Artículo escrito por patelnagendra1 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 *