C++ এ 1 থেকে n পর্যন্ত K সংখ্যা ব্যবহার করে সর্বাধিক XOR

এই সমস্যায়, আমাদের দুটি ধনাত্মক পূর্ণসংখ্যা n এবং k দেওয়া হয়েছে। আমাদের কাজ হল সর্বাধিক X সংখ্যা ব্যবহার করে 1 থেকে n এর মধ্যে সর্বাধিক xor বের করা

সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,

ইনপুট − n =5, k =2

আউটপুট − 7

ব্যাখ্যা −

elements till 5 is 1, 2, 3, 4, 5
Selecting all XOR pairs:
1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 4
2^3 = 4, 2^4 = 6, 2^5 = 7
3^4 = 7, 3^5 = 6
4^5 = 1
The maximum here is 7.

এই সমস্যাটি সমাধান করার জন্য, সংখ্যার যেকোন সমন্বয়ের জন্য সর্বাধিক XOR পাওয়া যেতে পারে যখন সংখ্যার সমস্ত বিট সেট করা হয়।

সুতরাং, সংখ্যাটি 5 হলে এর বাইনারি 101, সর্বাধিক XOR হবে 111 অর্থাৎ 7৷

কিন্তু যদি সর্বোচ্চ XOR-এর জন্য উপাদানের সংখ্যা 1 হয় তাহলে সর্বোচ্চ XOR হল 1৷ অন্যথায় সমস্ত বিট সেট করে সর্বাধিক XOR পাওয়া যাবে৷

উদাহরণ

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

#include <iostream>
using namespace std;
int maxXor(int n, int k) {
   if (k == 1)
      return n;
   int result = 1;
   while (result <= n)
      result <<= 1;
   return result - 1;
}
int main() {
   int n = 5, k = 2;
   cout<<"The maximum XOR of "<<k<<" numbers from 1 to"<<n<<" is "<<maxXor(n, k);
   return 0;
}

আউটপুট

The maximum XOR of 2 numbers from 1 to 5 is 7