Find the number of unique triples with XOR of zero using C++

In this article we will discuss about counting the number of unique triples (x, y, z) in a given array of unique numbers where their XOR is 0 . So the triple should be unique where all three elements are unique and the combination of all triples will be calculated like −

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.

Methods to find the solution

We know that the XOR operation with the same values ​​always results in zero. So an optimistic approach to finding unique triples is to find the XOR result of two values ​​in an array, store the result, and then search the array for a value equal to that result. Furthermore, the value of the result should not be equal to any pair of values. Please see

Example

#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

Explanation of the above code

• Create an unordered_set values ​​to store in the given array unique number.
• Use a for() loop to insert values ​​into the collection through values.insert(arr[i]).
• Use two nested loops to traverse all pairs of numbers and calculate their XOR values.
• Then, the array is searched for the XOR value, and the count is incremented when the value is in the array but not in the pair.
• Store the result as count / 3, so that the number of triples of three combinations can be calculated, and what we need is the only triple.

Conclusion

This article discussed how to find the number of triples with an XOR value of 0; we discussed an optimistic approach to finding unique triples. We also discussed a program in C to solve this problem. However, we can write this program in other programming languages ​​such as Java, C, Python, etc. Hope this article is helpful to you.

The above is the detailed content of Find the number of unique triples with XOR of zero using C++. For more information, please follow other related articles on the PHP Chinese website!