C++-এ অ্যারে থেকে ট্রিপলেটের সর্বোচ্চ XOR মান (Maximum XOR Value Among All Triplets)

এই সমস্যাতে, একটি পূর্ণসংখ্যা অ্যারে দেওয়া থাকে। আমাদের কাজ হল অ্যারে থেকে যেকোনো তিনটি উপাদান (triplet) নিয়ে তাদের XOR মান বের করুন এবং সে মধ্যে সর্বোচ্চ মানটি প্রিন্ট করুন।

উদাহরণ

ইনপুট: array = {5, 6, 1, 2}

আউটপুট: 6

ব্যাখ্যা:

5^6^1 = 2
5^6^2 = 1
5^1^2 = 6  ← সর্বোচ্চ
6^1^2 = 5

অপ্টিমাইজড পদ্ধতি

সরাসরি সব ট্রিপলেট চেক করলে O(n³) লেগে যায়। বেター পদ্ধতি:

প্রথমে সব জোড়া উপাদানের XOR একটি সেটে রাখুন
তারপর সেটের প্রতিটি মানকে অ্যারের প্রতিটি উপাদানের সাথে XOR করুন এবং সর্বোচ্চ মান বের করুন

সময় জটিলতা: O(n²)

C++ প্রোগ্রাম উদাহরণ

#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