C++の配列のすべてのトリプレット間のXORの最大値

この問題では、整数の配列が与えられます。私たちのタスクは、配列のすべてのトリプレットの中でXORの最大値を作成することです。

問題を理解するために例を見てみましょう

入力 −配列={5、6、1、2}

出力 − 6

説明 −

All triplets are:
5^6^1 = 2
5^6^2 = 1
5^1^2 = 6
6^1^2 = 5

この問題を解決するための直接的なアプローチは、考えられるすべてのトリプレットのXORを見つけて、すべてのトリプレットの最大値を出力することです。配列内に膨大な数の要素がある配列を操作する場合、これは効果的ではありません。

最大のXORを見つけるために、最初に要素のすべてのペアのXORを含むセットを作成します。次に、すべてのペアと要素の間のXORを見つけ、最大XORを見つけます。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int MaxTripletXor(int n, int a[]){
   set<int> XORpair;
   for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
         XORpair.insert(a[i] ^ a[j]);
      }
   }
   int maxXOR = 0;
   for (auto i : XORpair) {
      for (int j = 0; j < n; j++) {
         maxXOR = max(maxXOR, i ^ a[j]);
      }
   }
   return maxXOR;
}
int main(){
   int matrix[] = {1, 2, 3, 5, 7};
   int n = sizeof(matrix) / sizeof(matrix[0]);
   cout<<"The maximum XOR sum triplets is "<<MaxTripletXor(n, matrix);
   return 0;
}

出力

The maximum XOR sum triplets is 7