Número de tripletes en el arreglo que tienen el subarreglo xor igual

Dada una array de números enteros Arr . La tarea es contar el número de tripletes (i, j, k) tales que A i ^ A i+1 ^ A i+2 ^ …. ^ A j-1 = A j ^ A j+1 ^ A j+2 ^ ….. ^ A k , y 0 ≤i< j≤ k < N , donde N es el tamaño de la array.
Donde ^ es el xor bit a bit de dos números. 

Ejemplos: 

Entrada: Arr = {5, 2, 7} 
Salida: 2
Los tripletes son (0, 2, 2) ya que 5 ^ 2 = 7 y (0, 1, 2) ya que 2 ^ 7 = 5. 

Entrada: Arr = {1, 2, 3, 4, 5} 
Salida: 5

Enfoque de fuerza bruta: una solución simple es ejecutar tres bucles anidados iterando a través de todos los valores posibles de i , j y k y luego otro bucle para calcular el xor del primer y segundo subarreglo. 
La complejidad temporal de esta solución es O(N 4 ) .  

C++

// A simple C++ program to find Number of triplets
// in array having subarray xor equal
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
int xor_triplet(int arr[], int n)
{
    // Initialise result
    int ans = 0;
 
    // Pick 1st element of the triplet
    for (int i = 0; i < n; i++) {
 
        // Pick 2nd element of the triplet
        for (int j = i + 1; j < n; j++) {
 
            // Pick 3rd element of the triplet
            for (int k = j; k < n; k++) {
 
                int xor1 = 0, xor2 = 0;
 
                // Taking xor in the
                // first subarray
                for (int x = i; x < j; x++) {
                    xor1 ^= arr[x];
                }
 
                // Taking xor in the
                // second subarray
                for (int x = j; x <= k; x++) {
                    xor2 ^= arr[x];
                }
 
                // If both xor is equal
                if (xor1 == xor2) {
                    ans++;
                }
            }
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Calling
    cout << xor_triplet(arr, n);
    return 0;
}

Java

// Java program to find Number of triplets
// in array having subarray xor equal
class GFG
{
 
// Function to return the count
static int xor_triplet(int arr[], int n)
{
    // Initialise result
    int ans = 0;
 
    // Pick 1st element of the triplet
    for (int i = 0; i < n; i++)
    {
 
        // Pick 2nd element of the triplet
        for (int j = i + 1; j < n; j++)
        {
 
            // Pick 3rd element of the triplet
            for (int k = j; k < n; k++)
            {
                int xor1 = 0, xor2 = 0;
 
                // Taking xor in the
                // first subarray
                for (int x = i; x < j; x++)
                {
                    xor1 ^= arr[x];
                }
 
                // Taking xor in the
                // second subarray
                for (int x = j; x <= k; x++)
                {
                    xor2 ^= arr[x];
                }
 
                // If both xor is equal
                if (xor1 == xor2)
                {
                    ans++;
                }
            }
        }
    }
    return ans;
}
 
// Driver Code
public static void main (String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = arr.length;
 
    // Function Calling
    System.out.println(xor_triplet(arr, n));
}
}
 
// This code is contributed by AnkitRai01

Python3

# A simple python3 program to find Number of triplets
# in array having subarray xor equal
 
# Function to return the count
def xor_triplet(arr, n):
     
    # Initialise result
    ans = 0;
 
    # Pick 1st element of the triplet
    for i in range(n):
 
        # Pick 2nd element of the triplet
        for j in range(i + 1, n):
 
            # Pick 3rd element of the triplet
            for k in range(j, n):
 
                xor1 = 0; xor2 = 0;
 
                # Taking xor in the
                # first subarray
                for x in range(i, j):
                    xor1 ^= arr[x];
 
                # Taking xor in the
                # second subarray
                for x in range(j, k + 1):
                    xor2 ^= arr[x];
 
                # If both xor is equal
                if (xor1 == xor2):
                    ans += 1;
 
    return ans;
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5];
    n = len(arr);
 
    # Function Calling
    print(xor_triplet(arr, n));
     
# This code is contributed by PrinciRaj1992

C#

// C# program to find Number of triplets
// in array having subarray xor equal
using System;
     
class GFG
{
 
// Function to return the count
static int xor_triplet(int []arr, int n)
{
    // Initialise result
    int ans = 0;
 
    // Pick 1st element of the triplet
    for (int i = 0; i < n; i++)
    {
 
        // Pick 2nd element of the triplet
        for (int j = i + 1; j < n; j++)
        {
 
            // Pick 3rd element of the triplet
            for (int k = j; k < n; k++)
            {
                int xor1 = 0, xor2 = 0;
 
                // Taking xor in the
                // first subarray
                for (int x = i; x < j; x++)
                {
                    xor1 ^= arr[x];
                }
 
                // Taking xor in the
                // second subarray
                for (int x = j; x <= k; x++)
                {
                    xor2 ^= arr[x];
                }
 
                // If both xor is equal
                if (xor1 == xor2)
                {
                    ans++;
                }
            }
        }
    }
    return ans;
}
 
// Driver Code
public static void Main (String[] args)
{
    int []arr = { 1, 2, 3, 4, 5 };
    int n = arr.Length;
 
    // Function Calling
    Console.WriteLine(xor_triplet(arr, n));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// A simple Javascript program to find Number of triplets
// in array having subarray xor equal
 
 
// Function to return the count
function xor_triplet(arr, n) {
    // Initialise result
    let ans = 0;
 
    // Pick 1st element of the triplet
    for (let i = 0; i < n; i++) {
 
        // Pick 2nd element of the triplet
        for (let j = i + 1; j < n; j++) {
 
            // Pick 3rd element of the triplet
            for (let k = j; k < n; k++) {
 
                let xor1 = 0, xor2 = 0;
 
                // Taking xor in the
                // first subarray
                for (let x = i; x < j; x++) {
                    xor1 ^= arr[x];
                }
 
                // Taking xor in the
                // second subarray
                for (let x = j; x <= k; x++) {
                    xor2 ^= arr[x];
                }
 
                // If both xor is equal
                if (xor1 == xor2) {
                    ans++;
                }
            }
        }
    }
    return ans;
}
 
// Driver Code
 
let arr = [1, 2, 3, 4, 5];
let n = arr.length;
 
// Function Calling
document.write(xor_triplet(arr, n))
 
// This code is contributed by _saurabh_jaiswal
</script>
Producción

5

Complejidad temporal: O(N 4 )

Espacio Auxiliar: O(1)

Enfoque eficiente: 

  • Una solución eficiente es utilizar Trie .
  • Una observación es que si el subarreglo de i a k ​​tiene A i ^ A i+1 ^ …. ^ A k = 0 entonces podemos seleccionar cualquier j tal que i < j <= k y eso siempre satisfará nuestra condición.
  • Esta observación se utilizará para calcular el número de trillizos.
  • Tomaremos el xor acumulativo de los elementos en la array y verificaremos que este valor de xor exista en el Trie o no.
    1. Si el xor ya existe en el Trie , entonces hemos encontrado un subarreglo que tiene 0 xor y contamos todos los tripletes.
    2. De lo contrario, introduzca el valor de xor en el Trie .

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

C++

// C++ trie based program to find the Number of
// triplets in array having subarray xor equal
#include <bits/stdc++.h>
using namespace std;
 
// maximum number of bits
// in an integer <= 1e9
#define lg 31
 
// Structure of a Trie Node
struct TrieNode {
 
    // [0] index is bit 0
    // and [1] index is bit 1
    TrieNode* children[2];
 
    // Sum of indexes
    // inserted at a node
    int sum_of_indexes;
 
    // Number of indexes
    // inserted at a node
    int number_of_indexes;
 
    // Constructor to initialize
    // a newly created node
    TrieNode()
    {
 
        this->children[0] = nullptr;
        this->children[1] = nullptr;
        this->sum_of_indexes = 0;
        this->number_of_indexes = 0;
    }
};
 
// Function to insert curr_xor
// into the trie
void insert(TrieNode* node,
            int num,
            int index)
{
 
    // Iterate from the 31st bit
    // to the 0th bit of curr_xor
    // number
    for (int bits = lg; bits >= 0; bits--) {
 
        // Check if the current
        // bit is set or not
        int curr_bit = (num >> bits) & 1;
 
        // If this node isn't already
        // present in the trie structure
        // insert it into the trie.
        if (node->children[curr_bit]
            == nullptr) {
            node->children[curr_bit]
                = new TrieNode();
        }
 
        node = node->children[curr_bit];
    }
 
    // Increase the sum of
    // indexes by the current
    // index value
    node->sum_of_indexes += index;
 
    // Increase the number
    // of indexes by 1
    node->number_of_indexes++;
}
 
// Function to check if curr_xor
// is present in trie or not
int query(TrieNode* node,
          int num,
          int index)
{
 
    // Iterate from the 31st bit
    // to the 0th bit of curr_xor number
    for (int bits = lg; bits >= 0; bits--) {
 
        // Check if the current bit
        // is set or not
        int curr_bit = (num >> bits) & 1;
 
        // If this node isn't already
        // present in the trie structure
        // that means no sub array till
        // current index has 0 xor so
        // return 0
        if (node->children[curr_bit]
            == nullptr) {
            return 0;
        }
 
        node = node->children[curr_bit];
    }
 
    // Calculate the number of index
    // inserted at final node
    int sz = node->number_of_indexes;
 
    // Calculate the sum of index
    // inserted at final node
    int sum = node->sum_of_indexes;
 
    int ans = (sz * index) - (sum);
 
    return ans;
}
 
// Function to return the count of
// valid triplets
int no_of_triplets(int arr[], int n)
{
 
    // To store cumulative xor
    int curr_xor = 0;
 
    int number_of_triplets = 0;
 
    // The root of the trie
    TrieNode* root = new TrieNode();
 
    for (int i = 0; i < n; i++) {
 
        int x = arr[i];
 
        // Insert the curr_xor in the trie
        insert(root, curr_xor, i);
 
        // Update the cumulative xor
        curr_xor ^= x;
 
        // Check if the cumulative xor
        // is present in the trie or not
        // if present then add
        // (sz * index) - sum
        number_of_triplets
            += query(root, curr_xor, i);
    }
 
    return number_of_triplets;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 5, 2, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << no_of_triplets(arr, n);
 
    return 0;
}

Java

// Java trie based program to find the Number of
// triplets in array having subarray xor equal
class GFG
{
     
// maximum number of bits
// in an integer <= 1e9
static int lg = 31;
 
// Structure of a Trie Node
static class TrieNode
{
 
    // [0] index is bit 0
    // and [1] index is bit 1
    TrieNode children[];
 
    // Sum of indexes
    // inserted at at a node
    int sum_of_indexes;
 
    // Number of indexes
    // inserted at a node
    int number_of_indexes;
 
    // Constructor to initialize
    // a newly created node
    TrieNode()
    {
        children = new TrieNode[2];
        this.children[0] = null;
        this.children[1] = null;
        this.sum_of_indexes = 0;
        this.number_of_indexes = 0;
    }
};
 
// Function to insert curr_xor
// into the trie
static void insert(TrieNode node,
                    int num,
                    int index)
{
 
    // Iterate from the 31st bit
    // to the 0th bit of curr_xor
    // number
    for (int bits = lg; bits >= 0; bits--)
    {
 
        // Check if the current
        // bit is set or not
        int curr_bit = (num >> bits) & 1;
 
        // If this node isn't already
        // present in the trie structure
        // insert it into the trie.
        if (node.children[curr_bit]
            == null)
        {
            node.children[curr_bit]
                = new TrieNode();
        }
 
        node = node.children[curr_bit];
    }
 
    // Increase the sum of
    // indexes by the current
    // index value
    node.sum_of_indexes += index;
 
    // Increase the number
    // of indexes by 1
    node.number_of_indexes++;
}
 
// Function to check if curr_xor
// is present in trie or not
static int query(TrieNode node,
                  int num,
                  int index)
{
 
    // Iterate from the 31st bit
    // to the 0th bit of curr_xor number
    for (int bits = lg; bits >= 0; bits--)
    {
 
        // Check if the current bit
        // is set or not
        int curr_bit = (num >> bits) & 1;
 
        // If this node isn't already
        // present in the trie structure
        // that means no sub array till
        // current index has 0 xor so
        // return 0
        if (node.children[curr_bit]
            == null)
        {
            return 0;
        }
 
        node = node.children[curr_bit];
    }
 
    // Calculate the number of index
    // inserted at final node
    int sz = node.number_of_indexes;
 
    // Calculate the sum of index
    // inserted at final node
    int sum = node.sum_of_indexes;
 
    int ans = (sz * index) - (sum);
 
    return ans;
}
 
// Function to return the count of
// valid triplets
static int no_of_triplets(int arr[], int n)
{
 
    // To store cumulative xor
    int curr_xor = 0;
 
    int number_of_triplets = 0;
 
    // The root of the trie
    TrieNode root = new TrieNode();
 
    for (int i = 0; i < n; i++)
    {
 
        int x = arr[i];
 
        // Insert the curr_xor in the trie
        insert(root, curr_xor, i);
 
        // Update the cumulative xor
        curr_xor ^= x;
 
        // Check if the cumulative xor
        // is present in the trie or not
        // if present then add
        // (sz * index) - sum
        number_of_triplets
            += query(root, curr_xor, i);
    }
 
    return number_of_triplets;
}
 
// Driver Code
public static void main(String args[])
{
    // Given array
    int arr[] = { 5, 2, 7 };
    int n = arr.length;
 
    System.out.println(no_of_triplets(arr, n));
}
}
 
// This code is contributed by Arnab Kundu
Producción

2

Complejidad temporal: O(31*N) 
Espacio auxiliar : O(N).  

Publicación traducida automáticamente

Artículo escrito por FarhanTahir 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 *