XOR en un rango de una array binaria

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 
:
 

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *