Giá trị tối đa của XOR trong số tất cả các bộ ba của một mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng các số nguyên. Nhiệm vụ của chúng ta là tạo giá trị lớn nhất của XOR trong số tất cả các bộ ba của một mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng ={5, 6, 1, 2}

Đầu ra - 6

Giải thích -

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

Để giải quyết vấn đề này, một cách tiếp cận trực tiếp sẽ là tìm XOR của tất cả các bộ ba có thể có và in ra tối đa của tất cả các bộ ba. Điều này sẽ không hiệu quả nếu chúng ta làm việc với một mảng có số lượng lớn các phần tử trong mảng.

Để tìm XOR tối đa, trước tiên chúng ta sẽ tạo một tập hợp chứa XOR của tất cả các cặp phần tử. Sau đó, chúng tôi sẽ tìm XOR giữa tất cả các cặp và phần tử và tìm XOR tối đa.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

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

Đầu ra

The maximum XOR sum triplets is 7