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