N पूर्णांकों की एक सरणी और रेंज की Q क्वेरीज़ दी गई हैं। प्रत्येक क्वेरी के लिए, हमें रेंज में प्रत्येक संख्या के सबसे बड़े विषम भाजक का XOR लौटाना होगा।
सबसे बड़ा विषम भाजक वह सबसे बड़ी विषम संख्या है जो संख्या N को विभाजित कर सकती है, उदाहरण के लिए 6 का सबसे बड़ा विषम भाजक 3 है।
इनपुट: nums[] = { 3, 6, 7, 10 }, query[] = { { 0, 2 }, { 1, 3 } } आउटपुट: query1: 7 query2: 1 व्याख्या: nums सरणी के सबसे बड़े विषम भाजक हैं { 3, 3, 7, 5 }। क्वेरी 1 के लिए हमें इंडेक्स 0, 1, और 2 का XOR निकालना है जो 7 है, और क्वेरी 2 के लिए इंडेक्स 1, 2, और 3 का XOR जो 1 है।समाधान खोजने का दृष्टिकोण
सरल दृष्टिकोण
सरल दृष्टिकोण में, पहले हमें सरणी के सभी तत्वों के सबसे बड़े विषम भाजक निकालने होंगे। फिर क्वेरी की रेंज के अनुसार, उस रेंज में प्रत्येक तत्व का XOR निकालकर वापस करना होगा।
कुशल दृष्टिकोण
इस समस्या को हल करने का एक कुशल तरीका है सबसे बड़े विषम भाजक वाली सरणी का प्रीफिक्स XOR सरणी बनाना, ताकि हर बार रेंज में प्रत्येक संख्या का XOR निकालने के बजाय हम सीधे prefix_XOR[R] ^ prefix_XOR[L-1] से उत्तर प्राप्त कर सकें।
प्रीफिक्स XOR सरणी वह सरणी है जिसमें प्रत्येक तत्व पिछले सभी तत्वों का XOR होता है।
उदाहरण
#include <bits/stdc++.h> using namespace std; int main(){ int nums[] = { 3, 6, 7, 10 }; int n = sizeof(nums) / sizeof(nums[0]); int prefix_XOR[n]; // प्रत्येक तत्व का सबसे बड़ा विषम भाजक निकालकर सरणी बनाना for (int i = 0; i < n; i++) { while (nums[i] % 2 != 1) nums[i] /= 2; prefix_XOR[i] = nums[i]; } // prefix_XOR सरणी को प्रीफिक्स XOR सरणी में बदलना for (int i = 1; i < n; i++) prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i]; // क्वेरी सरणी जिसके परिणाम चाहिए int query[2][2] = {{0, 2},{1, 3}}; int q = sizeof(query) / sizeof(query[0]); // क्वेरीज़ के परिणाम निकालना for(int i = 0;i<q;i++){ if (query[i][0] == 0) cout<< prefix_XOR[query[i][1]] << endl; else{ int result = prefix_XOR[query[i][1]] ^ prefix_XOR[query[i][0] - 1]; cout << result << endl; } } return 0; }आउटपुट
7 1
उपरोक्त कोड की व्याख्या
prefix_XOR सरणी बनाई गई जिसमें प्रत्येक तत्व का सबसे बड़ा विषम भाजक स्टोर किया गया, फिर इसे प्रीफिक्स XOR सरणी में बदला गया।
सबसे बड़ा विषम भाजक 2 से तब तक विभाजित करके निकाला जाता है जब तक मॉड्यूलो 2 का परिणाम 1 न आ जाए।
प्रीफिक्स XOR सरणी सरणी को पार करके वर्तमान तत्व का पिछले तत्व के साथ बिटवाइज़ XOR करके बनाई जाती है।
क्वेरी का परिणाम prefix_XOR[R] ^ prefix_XOR[L-1] से निकाला जाता है।
निष्कर्ष
इस ट्यूटोरियल में हमने एक समस्या पर चर्चा की जहां दी गई सरणी की रेंज में प्रत्येक संख्या के सबसे बड़े विषम भाजक का XOR निकालना था। हमने सबसे बड़े विषम भाजक निकालकर और प्रीफिक्स XOR सरणी का उपयोग करके इसे हल करने का दृष्टिकोण बताया। साथ ही इस समस्या के लिए C++ प्रोग्राम भी दिया जिसे C, Java, Python आदि भाषाओं में भी लिखा जा सकता है। आशा है आपको यह लेख उपयोगी लगा होगा।
