C++を使用してXORがゼロである一意のトリプレットの数を見つける

この記事では、XORが0である一意の数の特定の配列内の一意のトリプレット（x、y、z）の数をカウントする方法について説明します。したがって、トリプレットは、3つの要素すべてが一意であり、すべてをカウントする一意である必要があります。たとえば、トリプレットの組み合わせ-

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.

解決策を見つけるためのアプローチ

同じ値のXORは常にゼロになることがわかっています。したがって、一意のトリプレットを見つけると、楽観的なアプローチを適用できます。これは、配列から2つの値のXORを見つけて結果を格納し、配列内の結果と等しい値を検索することです。また、結果の値は、ペアのどの値とも等しくてはなりません。

例

#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;
}

出力

Number of unique triplets : 3

上記のコードの説明

• unordered_set値のセットを作成します。特定の配列の一意の番号を格納します。
• for（）ループを使用して、values.insert（arr [i]）を使用してセットに値を挿入します。
• 2つのネストされたループを使用してすべてのペアをトラバースし、それらのXOR値を計算します。
• 次に、配列内のXOR値を検索し、値がペアではなく配列内にある場合はカウントをインクリメントします。
• 結果をcount/3として保存すると、トリプレットの3つの組み合わせがカウントされ、一意のトリプレットが必要になります。

結論

この記事では、XOR値が0のトリプレットの数を見つける方法について説明しました。ユニークなトリプレットを見つけるための楽観的なアプローチについて話し合いました。また、問題を解決するためのC++プログラムについても説明しました。ただし、このプログラムはJava、C、Pythonなどの他のプログラミング言語で作成できます。この記事がお役に立てば幸いです。