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.
- Si el xor ya existe en el Trie , entonces hemos encontrado un subarreglo que tiene 0 xor y contamos todos los tripletes.
- 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