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
Explicación:
Los tripletes son (0, 2, 2) ya que 5 ^ 2 = 7 y (0, 1, 2) ya que 2 ^ 7 = 5.
Entrada: Arr = [3, 6, 12, 8, 6, 2, 1, 5]
Salida: 6
Acercarse
- Simplifiquemos la expresión dada:
Ai ^ Ai + 1 ^ ...Aj - 1 = Aj ^ Aj + 1 ^ ...Ak Taking XOR with Aj ^ Aj + 1 ^ ...Ak on both sides Ai ^ Ai + 1 ^ ...Aj - 1 ^ Aj ^ Aj + 1 ^ ...Ak = 0
- Entonces, un subarreglo [i, k] que tenga XOR 0 tendrá k – i tripletes, porque cualquier j puede seleccionarse de [i+1, k] y el triplete cumplirá la condición.
- El problema ahora se reduce a encontrar longitudes de todos los subarreglos cuyo XOR sea 0 y para cada longitud L, agregue L – 1 a la respuesta.
- En la array de prefijos XOR, si en 2 índices, digamos L y R, el valor de prefijo XOR es el mismo, entonces significa que el XOR del subarreglo [L + 1, R] = 0.
- Para encontrar el conteo, almacenaremos lo siguiente:
Say we are at index i, and the prefix XOR at i = x. count[x] = Frequency of x in prefix XOR array before i ways[x] -> For each all j < i, if prefixXor[j] = x, then ways[x] += (j+1)
- Estos se pueden usar para contar los trillizos usando la fórmula:
Triplets += count[x] * i - ways[x]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the Number of
// triplets in array having subarray
// XOR equal
#include <bits/stdc++.h>
using namespace std;
// Function return the count of
// triplets having subarray XOR equal
int CountOfTriplets(int a[], int n)
{
int answer = 0;
// XOR value till i
int x = 0;
// Count and ways array as defined
// above
int count[100005] = { 0 };
int ways[100005] = { 0 };
for (int i = 0; i < n; i++)
{
x ^= a[i];
// Using the formula stated
answer += count[x] * i - ways[x];
// Increase the frequency of x
count[x]++;
// Add i+1 to ways[x] for upcoming
// indices
ways[x] += (i + 1);
}
return answer;
}
// Driver code
int main()
{
int Arr[] = { 3, 6, 12, 8, 6, 2, 1, 5 };
int N = sizeof(Arr) / sizeof(Arr[0]);
cout << CountOfTriplets(Arr, N);
return 0;
}
Java
// Java program to count the Number of
// triplets in array having subarray
// XOR equal
import java.io.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.lang.*;
import java.util.Collections;
class GFG
{
// Function return the count of
// triplets having subarray XOR equal
static int CountOfTriplets(int a[], int n)
{
int answer = 0;
// XOR value till i
int x = 0;
// Count and ways array as defined
// above
int count[] = new int[100005];
int ways[] = new int[100005];
for (int i = 0; i < n; i++)
{
x ^= a[i];
// Using the formula stated
answer += count[x] * i - ways[x];
// Increase the frequency of x
count[x]++;
// Add i+1 to ways[x] for upcoming
// indices
ways[x] += (i + 1);
}
return answer;
}
// Driver code
public static void main(String[] args)
{
int Arr[] = { 3, 6, 12, 8, 6, 2, 1, 5 };
int N = Arr.length;
System.out.print(CountOfTriplets(Arr, N));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program to count the Number of # triplets in array having subarray # XOR equal # Function return the count of # triplets having subarray XOR equal def CountOfTriplets(a,n): answer = 0 # XOR value till i x = 0 # Count and ways array as defined # above count = [0 for i in range(100005)] ways = [0 for i in range(100005)] for i in range(n): x ^= a[i] # Using the formula stated answer += count[x] * i - ways[x] # Increase the frequency of x count[x] += 1 # Add i+1 to ways[x] for upcoming # indices ways[x] += (i + 1) return answer # Driver code if __name__ == '__main__': Arr = [3, 6, 12, 8, 6, 2, 1, 5] N = len(Arr) print(CountOfTriplets(Arr, N)) # This code is contributed by Bhupendra_Singh
C#
// C# program to count the Number of
// triplets in array having subarray
// XOR equal
using System;
class GFG {
// Function return the count of
// triplets having subarray XOR equal
static int CountOfTriplets(int []a, int n)
{
int answer = 0;
// XOR value till i
int x = 0;
// Count and ways array as defined
// above
int []count = new int[100005];
int []ways = new int[100005];
for(int i = 0; i < n; i++)
{
x ^= a[i];
// Using the formula stated
answer += count[x] * i - ways[x];
// Increase the frequency of x
count[x]++;
// Add i+1 to ways[x] for upcoming
// indices
ways[x] += (i + 1);
}
return answer;
}
// Driver code
public static void Main(String[] args)
{
int []Arr = { 3, 6, 12, 8, 6, 2, 1, 5 };
int N = Arr.Length;
Console.Write(CountOfTriplets(Arr, N));
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript program to count the Number of
// triplets in array having subarray
// XOR equal
// Function return the count of
// triplets having subarray XOR equal
function CountOfTriplets(a, n)
{
let answer = 0;
// XOR value till i
let x = 0;
// Count and ways array as defined
// above
let count = new Array(100005);
let ways = new Array(100005);
count.fill(0);
ways.fill(0);
for (let i = 0; i < n; i++)
{
x ^= a[i];
// Using the formula stated
answer += count[x] * i - ways[x];
// Increase the frequency of x
count[x]++;
// Add i+1 to ways[x] for upcoming
// indices
ways[x] = ways[x] + i + 1;
}
return answer;
}
let Arr = [ 3, 6, 12, 8, 6, 2, 1, 5 ];
let N = Arr.length;
document.write(CountOfTriplets(Arr, N));
</script>
Producción:
6
Complejidad de tiempo : O(N)