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

上記のコードの説明を参照してください。

• 値を格納するunowned_setを作成します。指定された配列の一意の番号。
• for() ループを使用して、values.insert(arr[i]) を通じてコレクションに値を挿入します。
• 2 つのネストされたループを使用して、数値のすべてのペアを走査し、それらの XOR 値を計算します。
• 次に、配列内で XOR 値が検索され、値が配列内にあるがペア内にない場合、カウントが増分されます。
• 結果を count / 3 として保存し、3 つの組み合わせのトリプルの数を計算できるようにします。必要なのはトリプルだけです。

結論

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

以上がC++ を使用して、ゼロの XOR を持つ一意のトリプルの数を見つけます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。