इस समस्या में, हमें n तत्वों वाली एक सरणी arr[] और एक पूर्णांक k दिया गया है। हमारा कार्य आकार 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 खोजने के लिए। और फिर सभी में से अधिकतम लौटाएँ।
यह समाधान ठीक है लेकिन एक बेहतर दृष्टिकोण बनाया जा सकता है। हमें इंडेक्स 0 से शुरू होने वाली आकार k की उप-सरणी द्वारा योग खोजने की आवश्यकता है। और फिर सरणी पर पुनरावृति करके एक नए तत्व को XOR में जोड़ना और पहले को हटाना। विलोपन सूत्र x^a^x = a का उपयोग करके संभव है।
इसलिए, प्रत्येक पुनरावृत्ति के लिए हम पहले XOR ^ arr[i - k] करेंगे, जो अंतिम इंडेक्स + 1 से वर्तमान इंडेक्स - 1 तक की उप-सरणी का मान देगा।
फिर हम उप-सरणी के XOR को arr[i] के साथ करेंगे, वर्तमान XOR प्राप्त करने के लिए। हम सभी XOR में से अधिकतम मान खोजेंगे और लौटाएँगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
उदाहरण
#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