ค่า XOR สูงสุดของทริปเล็ตทั้งหมดในอาร์เรย์ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม งานของเราคือสร้างค่า XOR สูงสุดของทริปเล็ตทั้งหมดของอาร์เรย์

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต - array = {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