Programa Java para Número de tripletes únicos cuyo XOR es cero

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 temporal: O(n ³ )

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:  

1. Con el mapa, marque todos los elementos de la array.
2. Ejecute dos bucles anidados, uno desde in-1 y el otro desde i+1-n para obtener todos los pares.
3. Obtener el XOR del par.
4. Compruebe si el XOR es un elemento de array y no uno de _i o _j .
5. Aumente el conteo si la condición se mantiene.
6. 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:  

// 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)

Producción: 

2

Complejidad temporal: O(n ² )
 

Consulte el artículo completo sobre Número de trillizos únicos cuyo XOR es cero para obtener más detalles.