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