Dada una array arr[] que consta de N enteros distintos y consultas Q[][] del tipo {X, Y} , la tarea de cada consulta es encontrar el XOR bit a bit de todos los elementos de la array después de reemplazar X por Y en el formación.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5} Q = {(1, 4) (3, 6) (2, 3)}
Salida: 4 1 0
Explicación:
Consulta 1: La array se modifica a {4, 2, 3, 4, 5} y XOR = 4
Consulta 2: la array se modifica a {4, 2, 6, 4, 5} y XOR = 1
Consulta 3: la array se modifica a {4, 3, 6 , 4, 5} y XOR = 0
Entrada: arr[] = {5, 7, 8, 9, } Q = {(5, 6) (8, 1)}
Salida: 0 9
Explicación:
Consulta 1: La array se modifica a {6, 7, 8, 9} y XOR = 0
Consulta 2: la array se modifica a {6, 7, 1, 9} y XOR = 9
Enfoque:
El enfoque es usar la propiedad Bitwise XOR :
- Supongamos que hay tres elementos A, B y X , y su Xor es, total_xor = A ^ B ^ X.
- Para eliminar la contribución de X de total_xor , realice total_xor ^ X . Se puede verificar a partir del hecho de que A ^ B ^ X ^ X = A ^ B (XOR de un elemento consigo mismo es 0).
- Para sumar la contribución de Y en el total_xor , simplemente realice total_xor ^ Y.
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;
// Stores the bitwise XOR
// of array elements
int total_xor;
// Function to find the total xor
void initialize_xor(int arr[], int n)
{
// Loop to find the xor
// of all the elements
for (int i = 0; i < n; i++) {
total_xor = total_xor ^ arr[i];
}
}
// Function to find the XOR
// after replacing all occurrences
// of X by Y for Q queries
void find_xor(int X, int Y)
{
// Remove contribution of
// X from total_xor
total_xor = total_xor ^ X;
// Adding contribution of
// Y to total_xor
total_xor = total_xor ^ Y;
// Print total_xor
cout << total_xor << "\n";
}
// Driver Code
int main()
{
int arr[] = { 5, 7, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
initialize_xor(arr, n);
vector<vector<int> > Q = { { 5, 6 }, { 8, 1 } };
for (int i = 0; i < Q.size(); i++) {
find_xor(Q[i][0], Q[i][1]);
}
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Stores the bitwise XOR
// of array elements
static int total_xor;
// Function to find the total xor
static void initialize_xor(int arr[],
int n)
{
// Loop to find the xor
// of all the elements
for (int i = 0; i < n; i++)
{
total_xor = total_xor ^ arr[i];
}
}
// Function to find the XOR
// after replacing all occurrences
// of X by Y for Q queries
static void find_xor(int X, int Y)
{
// Remove contribution of
// X from total_xor
total_xor = total_xor ^ X;
// Adding contribution of
// Y to total_xor
total_xor = total_xor ^ Y;
// Print total_xor
System.out.print(total_xor + "\n");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 7, 8, 9 };
int n = arr.length;
initialize_xor(arr, n);
int [][]Q = { { 5, 6 }, { 8, 1 } };
for (int i = 0; i < Q.length; i++)
{
find_xor(Q[i][0], Q[i][1]);
}
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program to implement # the above approach # Stores the bitwise XOR # of array elements global total_xor total_xor = 0 # Function to find the total xor def initialize_xor(arr, n): global total_xor # Loop to find the xor # of all the elements for i in range(n): total_xor = total_xor ^ arr[i] # Function to find the XOR # after replacing all occurrences # of X by Y for Q queries def find_xor(X, Y): global total_xor # Remove contribution of # X from total_xor total_xor = total_xor ^ X # Adding contribution of # Y to total_xor total_xor = total_xor ^ Y # Print total_xor print(total_xor) # Driver Code if __name__ == '__main__': arr = [ 5, 7, 8, 9 ] n = len(arr) initialize_xor(arr, n) Q = [ [ 5, 6 ], [ 8, 1 ] ] # Function call for i in range(len(Q)): find_xor(Q[i][0], Q[i][1]) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Stores the bitwise XOR
// of array elements
static int total_xor;
// Function to find the total xor
static void initialize_xor(int []arr,
int n)
{
// Loop to find the xor
// of all the elements
for(int i = 0; i < n; i++)
{
total_xor = total_xor ^ arr[i];
}
}
// Function to find the XOR
// after replacing all occurrences
// of X by Y for Q queries
static void find_xor(int X, int Y)
{
// Remove contribution of
// X from total_xor
total_xor = total_xor ^ X;
// Adding contribution of
// Y to total_xor
total_xor = total_xor ^ Y;
// Print total_xor
Console.Write(total_xor + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 5, 7, 8, 9 };
int n = arr.Length;
initialize_xor(arr, n);
int [,]Q = { { 5, 6 }, { 8, 1 } };
for(int i = 0; i < Q.GetLength(0); i++)
{
find_xor(Q[i, 0], Q[i, 1]);
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Stores the bitwise XOR
// of array elements
let total_xor;
// Function to find the total xor
function initialize_xor(arr, n)
{
// Loop to find the xor
// of all the elements
for (let i = 0; i < n; i++)
{
total_xor = total_xor ^ arr[i];
}
}
// Function to find the XOR
// after replacing all occurrences
// of X by Y for Q queries
function find_xor(X, Y)
{
// Remove contribution of
// X from total_xor
total_xor = total_xor ^ X;
// Adding contribution of
// Y to total_xor
total_xor = total_xor ^ Y;
// Print total_xor
document.write(total_xor + "<br/>");
}
// Driver Code
let arr = [ 5, 7, 8, 9 ];
let n = arr.length;
initialize_xor(arr, n);
let Q = [[ 5, 6 ], [ 8, 1]];
for (let i = 0; i < Q.length; i++)
{
find_xor(Q[i][0], Q[i][1]);
}
</script>
Producción:
0 9
Complejidad de tiempo: O(N + tamaño de(Q))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por PratikLath y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA