इस समस्या में, हमें दो धनात्मक इंटीजर्स n और k दिए गए हैं। हमारा कार्य 1 से n तक अधिकतम XOR खोजना है अधिकतम X संख्याओं का उपयोग करके
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट − n = 5, k = 2
आउटपुट − 7
व्याख्या −
5 तक के एलिमेंट्स हैं 1, 2, 3, 4, 5 सभी XOR जोड़ियों का चयन: 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 यहां अधिकतम 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