इस समस्या में, हमें n तत्वों और aninteger k से मिलकर एक सरणी arr[] दी गई है। हमारा कार्य k आकार के उप-सरणी का अधिकतम XOR मान ज्ञात करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {3, 1, 6, 2 ,7, 9} k = 3 आउटपुट
12
स्पष्टीकरण
सभी उपसरणी और आकार k के सभी तत्वों का xor,
{3, 1, 6} = 4
{1, 6, 2} = 5
{6, 2, 7} = 3
{2, 7, 9} = 12 समाधान दृष्टिकोण
समस्या का एक सरल समाधान दो छोरों का उपयोग करना है। एक सरणी के ऊपर पुनरावृति करने के लिए और दूसरा उपसरणी के सभी तत्वों के XOR को खोजने के लिए। और फिर अधिकतम लौटाएं।
यह समाधान ठीक है लेकिन समस्या को हल करने के लिए एक बेहतर तरीका बनाया जा सकता है। हमें आकार k के उप-सरणी से शुरू करके योग को खोजने की आवश्यकता है
अनुक्रमणिका 0. और फिर सरणी को पुनरावृत्त करना और XOR में एक नया तत्व जोड़ना और पहले वाले को हटाना। सूत्र x^a^x =a का उपयोग करके हटाना संभव है।
इसलिए, प्रत्येक इंटरैक्शन के लिए हम पहले प्रदर्शन करेंगे, XOR ^ arr[i - k], जो पिछले इंडेक्स + 1 से वर्तमान इंडेक्स - 1 तक सबएरे का मान देगा।
फिर हम वर्तमान एक्सओआर प्राप्त करने के लिए एआर [i] के साथ सबएरे के एक्सओआर का प्रदर्शन करेंगे। हम सभी एक्सओआर में से अधिकतम मूल्य ढूंढेंगे और वापस कर देंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<iostream>
using namespace std;
int findMaxSubArrayXOR(int arr[] , int n , int k) {
int currentXORVal = 0 ;
for (int i = 0 ; i < k ; i++)
currentXORVal = currentXORVal ^ arr[i];
int maxXor = currentXORVal;
for (int i = k ; i < n; i++) {
currentXORVal = currentXORVal ^ arr[i-k];
currentXORVal = currentXORVal ^ arr[i];
maxXor = max(maxXor, currentXORVal);
}
return maxXor;
}
int main() {
int arr[] = {3, 1, 6, 2, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout<<"The maximum XOR of subarray of size "<<k<<" is "<<findMaxSubArrayXOR(arr, n, k);
return 0;
} आउटपुट
The maximum XOR of subarray of size 3 is 12