C++-এ একটি রেঞ্জ [L, R] থেকে দুটি পূর্ণসংখ্যার সর্বোচ্চ XOR মান (Maximum XOR Value of a Pair from a Range)

সমস্যা বিবরণ

একটি রেঞ্জ [L, R] দেওয়া আছে। এই রেঞ্জ থেকে দুটি পূর্ণসংখ্যা বেছে নেওয়া হবে যেন তাদের XOR মান সম্ভব সবচেয়ে বেশি হয়।

উদাহরণ: L = 1, R = 21 হলে আউটপুট হবে 31, কারণ 15 XOR 16 = 31 এবং এই রেঞ্জে এটি সর্বোচ্চ।

এলগরিদম

1. (L ^ R) মানটি বের করুন
2. এই মানের সবচেয়ে গুরুত্বপূর্ণ বিট (MSB) খুঁজুন
3. MSB থেকে সব বিট ১ করে ফলাফল তৈরি করুন

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

#include <bits/stdc++.h>
using namespace std;

int getMaxXOR(int L, int R) {
    int LXR = L ^ R;
    int msbPos = 0;
    while (LXR) {
        msbPos++;
        LXR >>= 1;
    }
    int maxXOR = 0;
    int two = 1;
    while (msbPos--) {
        maxXOR += two;
        two <<= 1;
    }
    return maxXOR;
}

int main() {
    int L = 1;
    int R = 21;
    cout << "Result = " << getMaxXOR(L, R) << endl;
    return 0;
}

আউটপুট

Result = 31