Dada una array binaria arr[] de tamaño N y algunas consultas. Cada consulta representa un rango de índice [l, r] . La tarea es encontrar el xor de los elementos en el rango de índice dado para cada consulta, es decir, arr[l] ^ arr[l + 1] ^ … ^ arr[r] .
Ejemplos:
Entrada: arr[] = {1, 0, 1, 1, 0, 1, 1}, q[][] = {{0, 3}, {0, 2}} Salida: 1 0 Consulta
1
:
arr
[ 0] ^ arr[1] ^ arr[2] ^ arr[3] = 1 ^ 0 ^ 1 ^ 1 = 1 Consulta 1:
arr[0] ^ arr[1] ^ arr[2] = 1 ^ 0 ^ 1 = 0
Entrada: arr[] = {1, 0, 1, 1, 0, 1, 1}, q[][] = {{1, 1}} Salida
: 0
Enfoque: La observación principal es que la respuesta requerida siempre será 0 o 1 . Si el número de 1 en el rango dado es impar, entonces la respuesta será 1 . De lo contrario 0 . Para responder múltiples consultas en tiempo constante, use una array de suma de prefijos pre[] donde pre[i] almacena el número de 1 en la array original en el rango de índice [0, i] que se puede usar para encontrar el número de 1 en cualquier rango de índice de la array dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return Xor in a range
// of a binary array
int xorRange(int pre[], int l, int r)
{
// To store the count of 1s
int cntOnes = pre[r];
if (l - 1 >= 0)
cntOnes -= pre[l - 1];
// If number of ones are even
if (cntOnes % 2 == 0)
return 0;
// If number of ones are odd
else
return 1;
}
// Function to perform the queries
void performQueries(int queries[][2], int q,
int a[], int n)
{
// To store prefix sum
int pre[n];
// pre[i] stores the number of
// 1s from pre[0] to pre[i]
pre[0] = a[0];
for (int i = 1; i < n; i++)
pre[i] = pre[i - 1] + a[i];
// Perform queries
for (int i = 0; i < q; i++)
cout << xorRange(pre, queries[i][0],
queries[i][1])
<< endl;
}
// Driver code
int main()
{
int a[] = { 1, 0, 1, 1, 0, 1, 1 };
int n = sizeof(a) / sizeof(a[0]);
// Given queries
int queries[][2] = { { 0, 3 }, { 0, 2 } };
int q = sizeof(queries) / sizeof(queries[0]);
performQueries(queries, q, a, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return Xor in a range
// of a binary array
static int xorRange(int pre[], int l, int r)
{
// To store the count of 1s
int cntOnes = pre[r];
if (l - 1 >= 0)
cntOnes -= pre[l - 1];
// If number of ones are even
if (cntOnes % 2 == 0)
return 0;
// If number of ones are odd
else
return 1;
}
// Function to perform the queries
static void performQueries(int queries[][], int q,
int a[], int n)
{
// To store prefix sum
int []pre = new int[n];
// pre[i] stores the number of
// 1s from pre[0] to pre[i]
pre[0] = a[0];
for (int i = 1; i < n; i++)
pre[i] = pre[i - 1] + a[i];
// Perform queries
for (int i = 0; i < q; i++)
System.out.println(xorRange(pre, queries[i][0],
queries[i][1]));
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 0, 1, 1, 0, 1, 1 };
int n = a.length;
// Given queries
int queries[][] = { { 0, 3 }, { 0, 2 } };
int q = queries.length;
performQueries(queries, q, a, n);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach # Function to return Xor in a range # of a binary array def xorRange(pre, l, r): # To store the count of 1s cntOnes = pre[r] if (l - 1 >= 0): cntOnes -= pre[l - 1] # If number of ones are even if (cntOnes % 2 == 0): return 0 # If number of ones are odd else: return 1 # Function to perform the queries def performQueries(queries, q, a, n): # To store prefix sum pre = [0 for i in range(n)] # pre[i] stores the number of # 1s from pre[0] to pre[i] pre[0] = a[0] for i in range(1, n): pre[i] = pre[i - 1] + a[i] # Perform queries for i in range(q): print(xorRange(pre, queries[i][0], queries[i][1])) # Driver code a = [ 1, 0, 1, 1, 0, 1, 1 ] n = len(a) # Given queries queries = [[ 0, 3 ], [ 0, 2 ]] q = len(queries) performQueries(queries, q, a, n) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return Xor in a range
// of a binary array
static int xorRange(int []pre, int l, int r)
{
// To store the count of 1s
int cntOnes = pre[r];
if (l - 1 >= 0)
cntOnes -= pre[l - 1];
// If number of ones are even
if (cntOnes % 2 == 0)
return 0;
// If number of ones are odd
else
return 1;
}
// Function to perform the queries
static void performQueries(int [,]queries, int q,
int []a, int n)
{
// To store prefix sum
int []pre = new int[n];
// pre[i] stores the number of
// 1s from pre[0] to pre[i]
pre[0] = a[0];
for (int i = 1; i < n; i++)
pre[i] = pre[i - 1] + a[i];
// Perform queries
for (int i = 0; i < q; i++)
Console.WriteLine(xorRange(pre, queries[i, 0],
queries[i, 1]));
}
// Driver code
public static void Main()
{
int []a = { 1, 0, 1, 1, 0, 1, 1 };
int n = a.Length;
// Given queries
int [,]queries = { { 0, 3 }, { 0, 2 } };
int q = queries.Length;
performQueries(queries, q, a, n);
}
}
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// Javascript implementation of the approach
// Function to return Xor in a range
// of a binary array
function xorRange(pre, l, r)
{
// To store the count of 1s
let cntOnes = pre[r];
if (l - 1 >= 0)
cntOnes -= pre[l - 1];
// If number of ones are even
if (cntOnes % 2 == 0)
return 0;
// If number of ones are odd
else
return 1;
}
// Function to perform the queries
function performQueries(queries, q, a, n)
{
// To store prefix sum
let pre = new Array(n);
// pre[i] stores the number of
// 1s from pre[0] to pre[i]
pre[0] = a[0];
for (let i = 1; i < n; i++)
pre[i] = pre[i - 1] + a[i];
// Perform queries
for (let i = 0; i < q; i++)
document.write(xorRange(pre, queries[i][0],
queries[i][1]) + "<br>");
}
// Driver code
let a = [ 1, 0, 1, 1, 0, 1, 1 ];
let n = a.length;
// Given queries
let queries = [ [ 0, 3 ], [ 0, 2 ] ];
let q = queries.length;
performQueries(queries, q, a, n);
</script>
1 0
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA