एन पूर्णांकों की एक सरणी और श्रेणियों के क्यू प्रश्नों को देखते हुए। प्रत्येक क्वेरी के लिए, हमें श्रेणी में प्रत्येक संख्या के सबसे बड़े विषम भाजक का XOR वापस करना होगा।
सबसे बड़ा विषम भाजक वह सबसे बड़ी विषम संख्या है जो संख्या N को विभाजित कर सकती है, उदा। उदाहरण के लिए, 6 का सबसे बड़ा विषम भाजक 3 है।
Input: nums[ ] = { 3, 6, 7, 10 }, query[ ] = { { 0, 2 }, { 1, 3 } }
Output:
query1: 7
query2: 1
Explanation: greatest odd divisors of nums array are { 3, 3, 7, 5 }.
For query 1 we need to find the XOR of indexes 0, 1, and 2 which is 7, and for query2 we need to find XOR of indexes 1, 2, and 3 which is 1. समाधान खोजने के लिए दृष्टिकोण
सरल तरीका
सबसे पहले, सरल दृष्टिकोण में, हमें सभी सरणी तत्वों के सबसे बड़े विषम भाजक को खोजने की आवश्यकता है। फिर क्वेरी की सीमा के अनुसार, हमें श्रेणी में प्रत्येक तत्व के XOR की गणना करने और वापस लौटने की आवश्यकता है।
कुशल दृष्टिकोण
इस समस्या को हल करने का एक प्रभावी तरीका यह है कि हर बार श्रेणी में प्रत्येक संख्या के XOR को खोजने के बजाय सबसे बड़ी विषम भाजक संख्या वाले सरणी का एक उपसर्ग XOR सरणी उपसर्ग_XOR [] बनाया जाए और उपसर्ग_XOR [R] - उपसर्ग_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];
// creating an array
// containing Greatest odd divisor of each element.
for (int i = 0; i < n; i++) {
while (nums[i] % 2 != 1)
nums[i] /= 2;
prefix_XOR[i] = nums[i];
}
// changing prefix_XOR array to prefix xor array.
for (int i = 1; i < n; i++)
prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];
// query array to find result of these queries.
int query[2][2] = {{0, 2},{1, 3}};
int q = sizeof(query) / sizeof(query[0]);
// finding results of queries.
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[0][1]] ^ prefix_XOR[query[i][0] - 1];
cout << result << endl;
}
}
return 0;
} आउटपुट
7 4
उपरोक्त कोड की व्याख्या
-
उपसर्ग_XOR सरणी प्रत्येक तत्व के सबसे बड़े विषम भाजक को संग्रहीत करने के लिए बनाई गई है और फिर इस सरणी को उपसर्ग XOR सरणी में बदल देती है।
-
सबसे बड़े विषम भाजक की गणना इसे दो से विभाजित करके की जाती है जब तक कि यह मॉड्यूल 2 1 नहीं देता है।
-
उपसर्ग xor सरणी सरणी के माध्यम से ट्रैवर्स करके और पिछले तत्व के साथ वर्तमान तत्व के बिटवाइज़ XOR करके बनाई गई है।
-
एक क्वेरी के परिणाम की गणना prefix_XOR[] सरणी के दाएँ अनुक्रमणिका को (बाएं -1) उपसर्ग_XOR[] सरणी के अनुक्रमणिका से घटाकर की जाती है।
निष्कर्ष
इस ट्यूटोरियल में, हमने एक समस्या पर चर्चा की जहां हमें दिए गए सरणी की सीमा में प्रत्येक संख्या के सबसे बड़े विषम भाजक के XOR को खोजने की आवश्यकता है। हमने प्रत्येक तत्व का सबसे बड़ा विषम भाजक ढूंढकर और उपसर्ग xor सरणी का उपयोग करके इस समस्या को हल करने के लिए एक दृष्टिकोण पर चर्चा की। हमने इस समस्या के लिए C++ प्रोग्राम पर भी चर्चा की जिसे हम प्रोग्रामिंग भाषाओं जैसे C, Java, Python, आदि के साथ कर सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।