Dados N números sin duplicados, cuente el número de tripletes únicos (a i , a j , a k ) tales que su XOR sea 0. Se dice que un triplete es único si los tres números del triplete son únicos.
Ejemplos:
Input : a[] = {1, 3, 5, 10, 14, 15};
Output : 2
Explanation : {1, 14, 15} and {5, 10, 15} are the
unique triplets whose XOR is 0.
{1, 14, 15} and all other combinations of
1, 14, 15 are considered as 1 only.
Input : a[] = {4, 7, 5, 8, 3, 9};
Output : 1
Explanation : {4, 7, 3} is the only triplet whose XOR is 0
Enfoque ingenuo : un enfoque ingenuo es ejecutar tres bucles anidados, el primero se ejecuta de 0 a n, el segundo de i+1 a n, y el último de j+1 a n para obtener los tripletes únicos. Calcule el XOR de a i , a j , a k , compruebe si es igual a 0. Si es así, aumente la cuenta.
Complejidad de tiempo: O(n 3 ), ya que usaremos bucles anidados para atravesar n 3 veces.
Espacio Auxiliar: O(1), ya que no utilizaremos espacio extra.
Enfoque eficiente : un enfoque eficiente es usar una de las propiedades de XOR: el XOR de dos de los mismos números da 0. Por lo tanto, necesitamos calcular el XOR de pares únicos únicamente, y si el XOR calculado es uno de los elementos de la array , luego obtenemos el triplete cuyo XOR es 0. A continuación se detallan los pasos para contar el número de tripletes únicos:
A continuación se muestra el algoritmo completo para este enfoque:
- Con el mapa, marque todos los elementos de la array.
- Ejecute dos bucles anidados, uno desde in-1 y el otro desde i+1-n para obtener todos los pares.
- Obtener el XOR del par.
- Compruebe si el XOR es un elemento de array y no uno de i o j .
- Aumente el conteo si la condición se mantiene.
- Regresa count/3 ya que solo queremos trillizos únicos. Como in y j+1-n nos dan pares únicos pero no trillizos, hacemos una cuenta/3 para eliminar las otras dos combinaciones posibles.
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to count the number of
// unique triplets whose XOR is 0
#include <bits/stdc++.h>
using namespace std;
// function to count the number of
// unique triplets whose xor is 0
int countTriplets(int a[], int n)
{
// To store values that are present
unordered_set<int> s;
for (int i = 0; i < n; i++)
s.insert(a[i]);
// stores the count of unique triplets
int count = 0;
// traverse for all i, j pairs such that j>i
for (int i = 0; i < n-1; i++) {
for (int j = i + 1; j < n; j++) {
// xor of a[i] and a[j]
int xr = a[i] ^ a[j];
// if xr of two numbers is present,
// then increase the count
if (s.find(xr) != s.end() && xr != a[i] &&
xr != a[j])
count++;
}
}
// returns answer
return count / 3;
}
// Driver code to test above function
int main()
{
int a[] = {1, 3, 5, 10, 14, 15};
int n = sizeof(a) / sizeof(a[0]);
cout << countTriplets(a, n);
return 0;
}
Java
// Java program to count
// the number of unique
// triplets whose XOR is 0
import java.io.*;
import java.util.*;
class GFG
{
// function to count the
// number of unique triplets
// whose xor is 0
static int countTriplets(int []a,
int n)
{
// To store values
// that are present
ArrayList<Integer> s =
new ArrayList<Integer>();
for (int i = 0; i < n; i++)
s.add(a[i]);
// stores the count
// of unique triplets
int count = 0;
// traverse for all i,
// j pairs such that j>i
for (int i = 0; i < n; i++)
{
for (int j = i + 1;
j < n; j++)
{
// xor of a[i] and a[j]
int xr = a[i] ^ a[j];
// if xr of two numbers
// is present, then
// increase the count
if (s.contains(xr) &&
xr != a[i] && xr != a[j])
count++;
}
}
// returns answer
return count / 3;
}
// Driver code
public static void main(String srgs[])
{
int []a = {1, 3, 5,
10, 14, 15};
int n = a.length;
System.out.print(countTriplets(a, n));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python 3 program to count the number of # unique triplets whose XOR is 0 # function to count the number of # unique triplets whose xor is 0 def countTriplets(a, n): # To store values that are present s = set() for i in range(n): s.add(a[i]) # stores the count of unique triplets count = 0 # traverse for all i, j pairs such that j>i for i in range(n): for j in range(i + 1, n, 1): # xor of a[i] and a[j] xr = a[i] ^ a[j] # if xr of two numbers is present, # then increase the count if (xr in s and xr != a[i] and xr != a[j]): count += 1; # returns answer return int(count / 3) # Driver code if __name__ == '__main__': a = [1, 3, 5, 10, 14, 15] n = len(a) print(countTriplets(a, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to count
// the number of unique
// triplets whose XOR is 0
using System;
using System.Collections.Generic;
class GFG
{
// function to count the
// number of unique triplets
// whose xor is 0
static int countTriplets(int []a,
int n)
{
// To store values
// that are present
List<int> s = new List<int>();
for (int i = 0; i < n; i++)
s.Add(a[i]);
// stores the count
// of unique triplets
int count = 0;
// traverse for all i,
// j pairs such that j>i
for (int i = 0; i < n; i++)
{
for (int j = i + 1;
j < n; j++)
{
// xor of a[i] and a[j]
int xr = a[i] ^ a[j];
// if xr of two numbers
// is present, then
// increase the count
if (s.Exists(item => item == xr) &&
xr != a[i] && xr != a[j])
count++;
}
}
// returns answer
return count / 3;
}
// Driver code
static void Main()
{
int []a = new int[]{1, 3, 5,
10, 14, 15};
int n = a.Length;
Console.Write(countTriplets(a, n));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Javascript
<script>
// javascript program to count
// the number of unique
// triplets whose XOR is 0
// function to count the
// number of unique triplets
// whose xor is 0
function countTriplets(a , n) {
// To store values
// that are present
var s = [];
for (i = 0; i < n; i++)
s.push(a[i]);
// stores the count
// of unique triplets
var count = 0;
// traverse for all i,
// j pairs such that j>i
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
// xor of a[i] and a[j]
var xr = a[i] ^ a[j];
// if xr of two numbers
// is present, then
// increase the count
if (s.includes(xr) && xr != a[i] && xr != a[j])
count++;
}
}
// returns answer
return count / 3;
}
// Driver code
var a = [ 1, 3, 5, 10, 14, 15 ];
var n = a.length;
document.write(countTriplets(a, n));
// This code contributed by Rajput-Ji
</script>
Producción:
2
Complejidad de tiempo : O (N * N), ya que estamos usando un bucle para atravesar N * N veces.
Espacio auxiliar : O(N), ya que estamos usando espacio extra para el conjunto s .