Cuente los subarreglos con una suma igual a su valor XOR

Dado un arreglo arr[] que contiene N elementos, la tarea es contar el número de sub-arreglos cuyo XOR de todos los elementos es igual a la suma de todos los elementos en el subarreglo. 
Ejemplos: 
 

Entrada: arr[] = {2, 5, 4, 6} 
Salida: 5 
Explicación: 
Todos los subarreglos {{2}, {5}, {4}, {6}} satisfacen la condición anterior ya que el XOR de los subarreglos es igual a la suma. Aparte de estos, el subarreglo {2, 5} también satisface la condición: 
(2 x o 5) = 7 = (2 + 5)
Entrada: arr[] = {1, 2, 3, 4, 5} 
Salida: 7 
 

Enfoque ingenuo: el enfoque ingenuo para este problema es considerar todos los subconjuntos y, para cada subarreglo, verificar si el XOR es igual a la suma. 
Complejidad Temporal: O(N ² )
Enfoque Eficiente: La idea es utilizar el concepto de ventana deslizante . Primero, calculamos la ventana para la cual se cumple la condición anterior y luego deslizamos a través de cada elemento hasta N. Se pueden seguir los siguientes pasos para calcular la respuesta: 
 

• Mantener dos punteros izquierdo y derecho inicialmente asignados a cero.
• Calcule la ventana usando el puntero derecho donde se cumple la condición A x o B = A + B.
• El recuento de los subconjuntos será de derecha a izquierda .
• Iterar a través de cada elemento y eliminar el elemento anterior.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to count the number
// of subarrays such that Xor of
// all the elements of that subarray
// is equal to sum of the elements
 
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to count the number
// of subarrays such that Xor of
// all the elements of that subarray
// is equal to sum of the elements
ll operation(int arr[], int N)
{
    // Maintain two pointers
    // left and right
    ll right = 0, ans = 0,
       num = 0;
 
    // Iterating through the array
    for (ll left = 0; left < N; left++) {
 
        // Calculate the window
        // where the above condition
        // is satisfied
        while (right < N
               && num + arr[right]
                      == (num ^ arr[right])) {
            num += arr[right];
            right++;
        }
 
        // Count will be (right-left)
        ans += right - left;
        if (left == right)
            right++;
 
        // Remove the previous element
        // as it is already included
        else
            num -= arr[left];
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << operation(arr, N);
}

// Java program to count the number
// of subarrays such that Xor of all
// the elements of that subarray is
// equal to sum of the elements
import java.io.*;
 
class GFG{
     
// Function to count the number
// of subarrays such that Xor of
// all the elements of that subarray
// is equal to sum of the elements
static long operation(int arr[], int N)
{
     
    // Maintain two pointers
    // left and right
    int right = 0;
    int    num = 0;
    long ans = 0;
 
    // Iterating through the array
    for(int left = 0; left < N; left++)
    {
        
       // Calculate the window
       // where the above condition
       // is satisfied
       while (right < N && num + arr[right] ==
                          (num ^ arr[right]))
       {
           num += arr[right];
           right++;
       }
        
       // Count will be (right-left)
       ans += right - left;
       if (left == right)
           right++;
        
       // Remove the previous element
       // as it is already included
       else
           num -= arr[left];
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = arr.length;
 
    System.out.println(operation(arr, N));
}
}
 
// This code is contributed by offbeat

# Python3 program to count the number
# of subarrays such that Xor of
# all the elements of that subarray
# is equal to sum of the elements
 
# Function to count the number
# of subarrays such that Xor of
# all the elements of that subarray
# is equal to sum of the elements
def operation(arr, N):
 
    # Maintain two pointers
    # left and right
    right = 0; ans = 0;
    num = 0;
 
    # Iterating through the array
    for left in range(0, N):
 
        # Calculate the window
        # where the above condition
        # is satisfied
        while (right < N and
               num + arr[right] ==
              (num ^ arr[right])):
            num += arr[right];
            right += 1;
 
        # Count will be (right-left)
        ans += right - left;
        if (left == right):
            right += 1;
 
        # Remove the previous element
        # as it is already included
        else:
            num -= arr[left];
 
    return ans;
 
# Driver code
arr = [1, 2, 3, 4, 5];
N = len(arr)
print(operation(arr, N));
 
# This code is contributed by Nidhi_biet

// C# program to count the number
// of subarrays such that Xor of all
// the elements of that subarray is
// equal to sum of the elements
using System;
class GFG{
     
// Function to count the number
// of subarrays such that Xor of
// all the elements of that subarray
// is equal to sum of the elements
static long operation(int []arr, int N)
{
     
    // Maintain two pointers
    // left and right
    int right = 0;
    int num = 0;
    long ans = 0;
 
    // Iterating through the array
    for(int left = 0; left < N; left++)
    {
         
        // Calculate the window
        // where the above condition
        // is satisfied
        while (right < N &&
               num + arr[right] ==
              (num ^ arr[right]))
        {
            num += arr[right];
            right++;
        }
             
        // Count will be (right-left)
        ans += right - left;
        if (left == right)
            right++;
             
        // Remove the previous element
        // as it is already included
        else
            num -= arr[left];
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 5 };
    int N = arr.Length;
 
    Console.WriteLine(operation(arr, N));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to count the number
// of subarrays such that Xor of
// all the elements of that subarray
// is equal to sum of the elements
 
// Function to count the number
// of subarrays such that Xor of
// all the elements of that subarray
// is equal to sum of the elements
function operation(arr, N)
{
    // Maintain two pointers
    // left and right
    let right = 0, ans = 0,
       num = 0;
 
    // Iterating through the array
    for (let left = 0; left < N; left++) {
 
        // Calculate the window
        // where the above condition
        // is satisfied
        while (right < N
               && num + arr[right]
                      == (num ^ arr[right])) {
            num += arr[right];
            right++;
        }
 
        // Count will be (right-left)
        ans += right - left;
        if (left == right)
            right++;
 
        // Remove the previous element
        // as it is already included
        else
            num -= arr[left];
    }
 
    return ans;
}
 
// Driver code
    let arr = [ 1, 2, 3, 4, 5 ];
    let N = arr.length;
 
    document.write(operation(arr, N));
 
</script>

7

Complejidad de tiempo: O(N) , donde N es la longitud de la array.