Dada una array arr[] de n enteros y algunas consultas. Cada consulta tiene la forma (L, R), donde L y R son índices de la array. Encuentre el valor XOR del subarreglo arr[L…R], es decir, el valor que se obtiene cuando todos los elementos en el rango [L, R] son XORed. Suponga que la indexación está basada en 0 y que cada elemento de la array es un entero sin signo de 32 bits.
Ejemplos:
Input : arr[] = {2, 5, 1, 6, 1, 2, 5}
L = 1, R = 4
Output : 3
The XOR value of arr[1...4] is 3.
Input : arr[] = {2, 5, 1, 6, 1, 2, 5}
L = 0, R = 6
Output : 6
The XOR value of arr[0...6] is 6.
Enfoque:
una solución simple es recorrer la array dada desde el índice L hasta el índice R para cada consulta. Esto da como resultado una complejidad de tiempo O(n) para procesar cada consulta. Si hay q consultas, entonces el tiempo total requerido será O(q*n). Para una gran cantidad de consultas y arrays grandes, esta solución no es óptima.
Una solución eficiente es preprocesar primero la array. Dos observaciones serán útiles:
- En el enunciado del problema se menciona que cada elemento de la array es un número sin signo de 32 bits. Por lo tanto, el resultado también será un número sin signo de 32 bits.
- Cuando se aplican XOR a múltiples bits, el resultado es 1 si hay un número impar de 1; de lo contrario, el resultado es 0.
Utilizando la observación 1, cree una array bidimensional cnt de tamaño 32*n. Esta array se utilizará para almacenar el recuento de 1s. Un elemento cnt[i][j] representa la cuenta del número de 1s para el i-ésimo bit hasta el índice j, es decir, cuántos 1s están presentes en el subarreglo arr[0..j] en la i-ésima posición del bit.
Según la observación 2, para obtener el valor XOR, es necesario encontrar el número de 1 para todas las posiciones de 32 bits en el subarreglo arr[L…R]. Esto se puede hacer con la ayuda de la array cnt. El número de unos para la i-ésima posición del bit en el subarreglo arr[L…R] es cnt[i][R] – cnt[i][L-1]. Si el número de 1 para el i-ésimo bit es impar, entonces el i-ésimo bit se establecerá como resultado. El resultado se puede obtener luego sumando la potencia de 2 correspondiente al i-ésimo bit si está establecido.
Procesar cada consulta de acuerdo con este algoritmo tomará O(32), es decir, tiempo constante. La etapa de preprocesamiento en la que se crea la array cnt tomará O (n) tiempo. Por lo tanto, la complejidad temporal total de esta solución para q consultas es O(n+q).
Implementación:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to preprocess the array and find count of
// number of ones upto jth index for ith bit.
void preprocess(int arr[], int n, vector<vector<int> >& cnt)
{
int i, j;
// Run a loop for each bit position from
// 0 to 32.
for (i = 0; i < 32; i++) {
cnt[i][0] = 0;
for (j = 0; j < n; j++) {
if (j > 0) {
// store previous count of 1s
// for ith bit position.
cnt[i][j] = cnt[i][j - 1];
}
// Check if ith bit for jth element
// of array is set or not. If it is
// set then increase count of 1 for
// ith bit by 1.
if (arr[j] & (1 << i))
cnt[i][j]++;
}
}
}
// Function to find XOR value for a range of array elements.
int findXOR(int L, int R, const vector<vector<int> > cnt)
{
// variable to store final answer.
int ans = 0;
// variable to store number of 1s for ith bit
// in the range L to R.
int noOfOnes;
int i, j;
// Find number of 1s for each bit position from 0
// to 32.
for (i = 0; i < 32; i++) {
noOfOnes = cnt[i][R] - ((L > 0) ? cnt[i][L - 1] : 0);
// If number of 1s are odd then in the result
// ith bit will be set, i.e., 2^i will be present in
// the result. Add 2^i in ans variable.
if (noOfOnes & 1) {
ans += (1 << i);
}
}
return ans;
}
int main()
{
int arr[] = { 2, 5, 1, 6, 1, 2, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int> > cnt(32, vector<int>(n));
preprocess(arr, n, cnt);
int L = 1;
int R = 4;
cout << findXOR(L, R, cnt);
return 0;
}
Java
class GFG
{
// Function to preprocess the array and find count of
// number of ones upto jth index for ith bit.
static void preprocess(int arr[], int n, int[][] cnt)
{
int i, j;
// Run a loop for each bit position from
// 0 to 32.
for (i = 0; i < 32; i++)
{
cnt[i][0] = 0;
for (j = 0; j < n; j++)
{
if (j > 0)
{
// store previous count of 1s
// for ith bit position.
cnt[i][j] = cnt[i][j - 1];
}
// Check if ith bit for jth element
// of array is set or not. If it is
// set then increase count of 1 for
// ith bit by 1.
if ((arr[j] & (1 << i)) >= 1)
cnt[i][j]++;
}
}
}
// Function to find XOR value for a range of array elements.
static int findXOR(int L, int R, int[][] cnt)
{
// variable to store final answer.
int ans = 0;
// variable to store number of 1s for ith bit
// in the range L to R.
int noOfOnes;
int i, j;
// Find number of 1s for each bit position from 0
// to 32.
for (i = 0; i < 32; i++)
{
noOfOnes = cnt[i][R] - ((L > 0) ? cnt[i][L - 1] : 0);
// If number of 1s are odd then in the result
// ith bit will be set, i.e., 2^i will be present in
// the result. Add 2^i in ans variable.
if (noOfOnes % 2 == 1)
{
ans += (1 << i);
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 5, 1, 6, 1, 2, 5 };
int n = arr.length;
int[][] cnt = new int[32][n];
preprocess(arr, n, cnt);
int L = 1;
int R = 4;
System.out.print(findXOR(L, R, cnt));
}
}
// This code is contributed by Rajput-Ji
Python3
# Function to preprocess the array and # find count of number of ones upto # jth index for ith bit. def preprocess(arr, n, cnt): # Run a loop for each bit position # from 0 to 32. for i in range(32): cnt[i][0] = 0 for j in range(n): if (j > 0): # store previous count of 1s # for ith bit position. cnt[i][j] = cnt[i][j - 1] # Check if ith bit for jth element # of array is set or not. If it is # set then increase count of 1 for # ith bit by 1. if (arr[j] & (1 << i)): cnt[i][j] += 1 # Function to find XOR value # for a range of array elements. def findXOR(L, R, cnt): # variable to store final answer. ans = 0 # variable to store number of 1s # for ith bit in the range L to R. noOfOnes = 0 # Find number of 1s for each # bit position from 0 to 32. for i in range(32): if L > 0: noOfOnes = cnt[i][R] - cnt[i][L - 1] else: noOfOnes = cnt[i][R] # If number of 1s are odd then in the result # ith bit will be set, i.e., 2^i will be # present in the result. Add 2^i in ans variable. if (noOfOnes & 1): ans += (1 << i) return ans # Driver Code arr = [2, 5, 1, 6, 1, 2, 5] n = len(arr) cnt = [[0 for i in range(n)] for i in range(32)] preprocess(arr, n, cnt) L = 1 R = 4 print(findXOR(L, R, cnt)) # This code is contributed by Mohit Kumar
C#
using System;
class GFG
{
// Function to preprocess the array and find count of
// number of ones upto jth index for ith bit.
static void preprocess(int []arr, int n, int[,] cnt)
{
int i, j;
// Run a loop for each bit position from
// 0 to 32.
for (i = 0; i < 32; i++)
{
cnt[i, 0] = 0;
for (j = 0; j < n; j++)
{
if (j > 0)
{
// store previous count of 1s
// for ith bit position.
cnt[i, j] = cnt[i, j - 1];
}
// Check if ith bit for jth element
// of array is set or not. If it is
// set then increase count of 1 for
// ith bit by 1.
if ((arr[j] & (1 << i)) >= 1)
cnt[i, j]++;
}
}
}
// Function to find XOR value for a range of array elements.
static int findXOR(int L, int R, int[,] cnt)
{
// variable to store readonly answer.
int ans = 0;
// variable to store number of 1s for ith bit
// in the range L to R.
int noOfOnes;
int i;
// Find number of 1s for each bit position from 0
// to 32.
for (i = 0; i < 32; i++)
{
noOfOnes = cnt[i, R] - ((L > 0) ? cnt[i, L - 1] : 0);
// If number of 1s are odd then in the result
// ith bit will be set, i.e., 2^i will be present in
// the result. Add 2^i in ans variable.
if (noOfOnes % 2 == 1)
{
ans += (1 << i);
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 2, 5, 1, 6, 1, 2, 5 };
int n = arr.Length;
int[,] cnt = new int[32, n];
preprocess(arr, n, cnt);
int L = 1;
int R = 4;
Console.Write(findXOR(L, R, cnt));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Function to preprocess the array and find count of
// number of ones upto jth index for ith bit.
function preprocess(arr, n, cnt)
{
var i, j;
// Run a loop for each bit position from
// 0 to 32.
for (i = 0; i < 32; i++) {
cnt[i][0] = 0;
for (j = 0; j < n; j++) {
if (j > 0) {
// store previous count of 1s
// for ith bit position.
cnt[i][j] = cnt[i][j - 1];
}
// Check if ith bit for jth element
// of array is set or not. If it is
// set then increase count of 1 for
// ith bit by 1.
if (arr[j] & (1 << i))
cnt[i][j]++;
}
}
}
// Function to find XOR value for a range of array elements.
function findXOR(L, R, cnt)
{
// variable to store final answer.
var ans = 0;
// variable to store number of 1s for ith bit
// in the range L to R.
var noOfOnes;
var i, j;
// Find number of 1s for each bit position from 0
// to 32.
for (i = 0; i < 32; i++) {
noOfOnes = cnt[i][R] - ((L > 0) ? cnt[i][L - 1] : 0);
// If number of 1s are odd then in the result
// ith bit will be set, i.e., 2^i will be present in
// the result. Add 2^i in ans variable.
if (noOfOnes & 1) {
ans += (1 << i);
}
}
return ans;
}
var arr = [ 2, 5, 1, 6, 1, 2, 5 ];
var n = arr.length;
var cnt = Array.from( Array(32), () => Array(n));
preprocess(arr, n, cnt);
var L = 1;
var R = 4;
document.write( findXOR(L, R, cnt));
// This code is contributed by itsok.
</script>
3
Complejidad temporal: O(n+q)
Espacio auxiliar: O(n)