सी++ में सभी सबअरे एक्सओआर का एक्सओआर

इस समस्या में, हमें n तत्वों की एक सरणी दी गई है। हमारा काम सरणी के तत्वों से बनाए गए सभी संभावित उप-सरणी (क्रम में लिया गया) के XOR के XOR को प्रिंट करना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट - सरणी ={1, 3, 6, 8}

आउटपुट - 0

स्पष्टीकरण -

(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6)^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)

इस समस्या को हल करने के लिए, एक सरल समाधान सभी उप-सरणी पर पुनरावृति हो सकता है और xors ढूंढ सकता है। लेकिन यह एक अक्षम तरीका है। एक बेहतर तरीका यह हो सकता है कि सभी उप-सरणी में होने वाले सरणी के प्रत्येक तत्व की आवृत्ति की गणना की जाए और xor के गुण का उपयोग किया जाए - तत्व की xor सम संख्या 0 है . इसका उपयोग करके हम उप-सरणी सूची में कई बार होने वाले सभी मानों को अनदेखा कर देंगे, अब विषम घटना आवृत्ति वाले तत्वों पर विचार किया जाना चाहिए यानी विषम घटना आवृत्ति वाले तत्वों का xor अंतिम परिणाम देगा।

सरणी के प्रत्येक तत्व की उप-सरणी में होने का पता लगाने के लिए, हम इस सूत्र का उपयोग करेंगे (i+1)*(n-i) ।

इस सूत्र का उपयोग करके, हम प्रत्येक तत्व की घटना की आवृत्ति का पता लगाएंगे और फिर उन तत्वों पर विचार करेंगे जिनकी एक विषम आवृत्ति है, या फिर अंतिम परिणाम प्राप्त करने के लिए।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,

#include <iostream>
using namespace std;
   int xorSubarrayXors(int arr[], int N){
   int result = 0;
   for (int i = 0; i < N; i++){
      int freqency = (i + 1) * (N - i);
      if (freqency % 2 == 1)
         result ^= arr[i];
   }
   return result;
}
int main() {
   int arr[] = {1, 3, 6, 8};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The xor of all subarray xors is : "<<xorSubarrayXors(arr, N);
   return 0;
}

आउटपुट

The xor of all subarray xors is : 0