Trouver le nombre de triples uniques avec XOR de zéro en utilisant C++

Dans cet article, nous parlerons du comptage du nombre de triples uniques (x,y,z) dans un tableau donné de nombres uniques où leur XOR est 0. Ainsi, un triplet doit être unique où les trois éléments sont uniques et la combinaison de tous les triples sera calculée comme −

Input : arr[ ] = { 5, 6, 7, 1, 3 }
Output : 2
Explanation : triplets are { 5, 6, 3 } and { 6, 7, 1 } whose XOR is zero.

Input : arr[ ] = { 3, 6, 8, 1, 5, 4 , 12}
Output : 3
Explanation : Triplets are { 3, 6, 5 }, { 1, 5, 4 } and { 4, 8, 12 } whose XOR is zero.

Façons de trouver la solution

Nous connaissons l'opération XOR pour les mêmes valeurs Le résultat est toujours nul. Ainsi, une approche optimiste pour trouver des triplets uniques consiste à trouver le résultat XOR de deux valeurs dans un tableau, à stocker le résultat, puis à rechercher dans le tableau une valeur égale à ce résultat. De plus, la valeur du résultat ne doit être égale à aucune paire de valeurs. Veuillez consulter

Exemple

#include <bits/stdc++.h>
using namespace std;

int main () {
   int arr[] = { 3, 6, 8, 1, 5, 4, 12 };
   int n = sizeof (arr) / sizeof (arr[0]);
   int result;
   // count variable to keep count of pairs.
   int count = 0;
   // creating a set to store unique numbers .
   unordered_set < int >values;
   // inserting values in set.
   for (int i = 0; i < n; i++)
      values.insert (arr[i]);


   // traverse for all pairs to calculate XOR.
   for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) { // finding xor of i, j pair.
         int XR = arr[i] ^ arr[j];

         // checking if XOR value of pair present in array
         // and value should not be in pairs.
         if (values.find (XR) != values.end () && XR != arr[i] &&
            XR != arr[j])
            count++;
      }

   }
   // storing result
   result = count / 3;
   cout << "Number of unique triplets : " << result;
   return 0;
}

Output

Number of unique triplets : 3

Explication du code ci-dessus

• Créez un unordered_set valeurs pour stocker les nombres uniques dans le tableau donné.
• Utilisez une boucle for() pour insérer des valeurs dans la collection via values.insert(arr[i]).
• Utilisez deux boucles imbriquées pour parcourir toutes les paires de nombres et calculer leurs valeurs XOR.
• Ensuite, recherchez dans le tableau la valeur XOR et incrémentez le nombre lorsque la valeur est dans le tableau mais pas dans la paire.
• Stockez le résultat sous forme de compte / 3, afin que le nombre de triplets de trois combinaisons puisse être calculé, et ce dont nous avons besoin est le seul triple.

Conclusion

Cet article explique comment trouver le nombre de triplets avec une valeur XOR 0 ; nous avons discuté d'une approche optimiste pour trouver des triplets uniques. Nous avons également discuté d'un programme pour résoudre ce problème en C++. Cependant, nous pouvons écrire ce programme dans d'autres langages de programmation tels que Java, C, Python, etc. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!