एक समस्या को हल करने के लिए जिसमें हमें एक सरणी और कुछ क्वेरीज़ दी गई हैं। अब प्रत्येक क्वेरी में, हमें एक रेंज दी गई है। अब हमें एक संख्या ढूंढनी है जिससे उनके साथ XOR का योग अधिकतम हो, उदाहरण के लिए
इनपुट: A = {20, 11, 18, 2, 13} तीन क्वेरीज़ (L, R) जोड़े के रूप में 1 3 3 5 2 4 आउटपुट: 2147483629 2147483645 2147483645इस समस्या में, हम प्रत्येक स्थिति पर संख्याओं में मौजूद 1 की प्रीफिक्स गिनती लेने जा रहे हैं अब चूंकि हमने अपने 1 की संख्या को प्रीकैलकुलेट कर लिया है, इसलिए दी गई रेंज L से R में 1 की संख्या खोजने के लिए, हमें R तक प्रीफिक्स को L तक प्रीफिक्स से घटाना होगा।
समाधान खोजने का दृष्टिकोण
इस दृष्टिकोण में, चूंकि हमें अधिकतम योग ढूंढना आवश्यक है, इसलिए हमें XOR के अधिकांश बिट्स को 1 बनाने की आवश्यकता है; इसलिए हम चेक करते हैं कि किसी भी बिट के लिए यदि 1 की संख्या 0 की संख्या से अधिक है तो हम x के उस बिट को रीसेट करते हैं क्योंकि अब अधिकांश संख्या में वह बिट 1 के बराबर है इसलिए जब हम उस बहुसंख्यक 1 को 0 के साथ जोड़ते हैं तो अंततः हमारे पास उस बिट का बहुसंख्यक 1 के बराबर होता है इस प्रकार हम अपना उत्तर अधिकतम करते हैं।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <bits/stdc++.h> using namespace std; #define MAX 2147483647 // 2^31 - 1 int prefix[100001][32]; // प्रीफिक्स सरणी void prefix_bit(int A[], int n){ // प्रत्येक स्थिति पर मौजूद 1 की प्रीफिक्स गिनती लेना for (int j = 0; j < 32; j++) // हम 0th गिनती को 0 रखते हैं और हमारी प्रीफिक्स सरणी इंडेक्स 1 से शुरू होती है prefix[0][j] = 0; for (int i = 1; i <= n; i++){ // हमारी प्रीफिक्स सरणी बनाना int a = A[i - 1]; // ith तत्व for (int j = 0; j < 32; j++){ // चूंकि हमारी संख्या 2^32 से कम है इसलिए हम बिट 0 से 31 तक पार करते हैं int x = 1 << j; // बिट्स में पार करना if (a & x) // यदि यह बिट 1 है तो हम प्रीफिक्स गिनती को पिछलागिनती + 1 बनाते हैं prefix[i][j] = 1 + prefix[i - 1][j]; else prefix[i][j] = prefix[i - 1][j]; } } } int maximum_num(int l, int r){ int numberofbits = r - l + 1; // रेंज में तत्वों की संख्या इसलिए बिट्स की संख्या int X = MAX; // हम अधिकतम मान लेते हैं जैसे कि इसके सभी बिट्स 1 हैं // प्रत्येक बिट पर पुनरावृति for (int i = 0; i < 31; i++){ int x = prefix[r][i] - prefix[l - 1][i]; // दी गई रेंज में सेट बिट्स की संख्या निकालना if (x >= numberofbits - x){ // यदि 1 की संख्या 0 की संख्या से अधिक या बराबर है int currentbit = 1 << i; // हम वर्तमान बिट को टॉगल करने के लिए प्रीफिक्स सेट करते हैं X = X ^ currentbit; // हम उस बिट को 1 से 0 में टॉगल करते हैं } } return X; // उत्तर } int main(){ int n = 5, q = 3; // हमारी सरणी में तत्वों की संख्या और मौजूद क्वेरीज़ की संख्या int A[] = { 210, 11, 48, 22, 133 }; // हमारी सरणी में तत्व int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // दी गई क्वेरीज़ prefix_bit(A, n); // प्रीफिक्स बिट सरणी बनाना for (int i = 0; i < q; i++) cout << maximum_num(L[i], R[i]) << "\n"; return 0; }आउटपुट
2147483629 2147483647 2147483629
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम पहले प्रत्येक बिट के लिए मौजूद 1 की प्रीफिक्स गिनती निकालते हैं। अब जब हमें यह गिनती मिल जाती है, तो हमने अपनी सबसे बड़ी समस्या हल कर ली है जो क्वेरीज़ को पार करना था। अब हम प्रत्येक रेंज को पार नहीं करने जा रहे हैं। इसलिए हम इसे अपनी प्रीफिक्स सरणी के माध्यम से निकाल सकते हैं। अब हमारा मुख्य तर्क यह है कि हम रेंज में रीसेट और सेट बिट्स की संख्या की गणना करते हैं जब हम एक ऐसी स्थिति का सामना करते हैं जहां सेट बिट की संख्या रीसेट बिट की संख्या से अधिक होती है। इसलिए, हम अपने x में उस बिट को रीसेट करते हैं अब चूंकि हमने x को 2^31 - 1 से इनिशियलाइज़ किया है इसलिए इसके सभी बिट्स सेट होंगे, और हम x में बिट्स को टॉगल करके अपना उत्तर ढूंढते हैं।
निष्कर्ष
इस ट्यूटोरियल में, हम दी गई सरणी रेंज के साथ XOR योग अधिकतम करने वाली संख्या ढूंढने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य) भी सीखा जिससे हमने इस समस्या को हल किया। हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।