Giá trị lớn nhất của XOR trong 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 cho một mảng các số nguyên. Nhiệm vụ là tạo giá trị lớn nhất của XOR trong tất cả các bộ ba của một mảng.

Hãy xem một ví dụ để hiểu bài toán:

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

Đầu ra – 6

Giải thích –

Tất cả các bộ ba:
5^6^1 = 2
5^6^2 = 1
5^1^2 = 6
6^1^2 = 5

Để giải quyết bài toá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ể và in ra giá trị lớn nhất của tất cả các bộ ba. Cách này sẽ không hiệu quả nếu làm việc với mảng có số lượng phần tử lớn.

Để tìm XOR lớn nhất, chúng ta sẽ trước tiên 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 ta sẽ tìm XOR giữa tất cả các cặp và phần tử, và tìm các XOR lớn nhất.

Ví dụ

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

#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<<"Giá trị XOR lớn nhất của các bộ ba là "<<MaxTripletXor(n, matrix);
    return 0;
}

Kết quả

Giá trị XOR lớn nhất của các bộ ba là 7