使用 C++ 找出 XOR 为零的唯一三元组的数量

  • Z时代
  • 2024-01-10
  • 分类：综合

在本文中，我们将讨论计算给定的唯一数字数组中唯一三元组 (x, y, z) 的数量，其中它们的 XOR 为 0。因此，三元组应该是唯一的，其中所有三个元素都是唯一的，并且会计算所有例如三胞胎的组合 -

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.

寻找解决方案的方法

我们知道相同值的异或总是为零。所以我们找到唯一的三元组，可以应用一种乐观的方法，即从数组中找到两个值的异或并存储结果，并在数组中搜索与结果相等的值。此外，结果的值不应成对等于任何值。寻找

示例

#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;
   // 计数变量以保持对的计数。
   int count = 0;
   // 创建一个集合来存储唯一的数字。
   unordered_set < int >values;
   // 在集合中插入值。
   for (int i = 0; i < n; i++)
     values.insert(arr[i]);
   // 遍历所有对以计算 XOR。
   for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) { // 找到 i, j 对的异或。
         int XR = arr[i] ^ arr[j];
         // 检查数组中是否存在对的 XOR 值
         // 和值不应成对出现。
         if (values.find (XR) !=values.end() && XR != arr[i] &&
            XR != arr[j])
            count++;
      }
   }
   // 存储结果
   result = count / 3;
   cout << "独特三胞胎的数量： " << result;
   return 0;
}
输出结果
独特三胞胎的数量： 3

上面代码的解释

  • 创建一组 unordered_set < int > 值；存储给定数组的唯一编号。

  • 使用for()循环在使用values.insert(arr[i]) 的集合中插入值。

  • 使用两个嵌套循环遍历所有对并计算它们的 XOR 值。

  • 然后，搜索数组中的 XOR 值，如果该值是在数组中而不是成对找到的，则增加计数。

  • 将结果存储为 count / 3 将计算三元组的三个组合，我们需要唯一的三元组。

结论

这篇文章讨论了寻找 XOR 值为 0 的三元组的数量；我们讨论了一种寻找独特三胞胎的乐观方法。我们还讨论了C++程序来解决这个问题。但是，我们可以使用任何其他编程语言（如 Java、C、Python 等）编写此程序。我们希望本文对您有所帮助。

以上是 使用 C++ 找出 XOR 为零的唯一三元组的数量 的全部内容， 来源链接： utcz.com/z/361993.html

回到顶部