इस समस्या में, हमें n तत्वों की एक सरणी दी गई है। हमारा कार्य सरणी के तत्वों से बने सभी संभावित सबएरे (क्रम में लिए गए) के XORs का XOR प्रिंट करना है।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट - array = {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)
इस समस्या को हल करने के लिए, एक सरल समाधान सभी सबएरे पर पुनरावृति करना और XOR खोजना हो सकता है। लेकिन यह एक अकुशल दृष्टिकोण है। एक बेहतर दृष्टिकोण सरणी के प्रत्येक तत्व की आवृत्ति गिनना हो सकता है जो सभी सबएरे में हुई और XOR के गुण का उपयोग करें - तत्व का सम संख्या में XOR 0 होता है। इसका उपयोग करके हम उन सभी मानों को अनदेखा करेंगे जो सब-एरे सूची में सम संख्या में होते हैं, अब विषम घटना आवृत्ति वाले तत्वों पर विचार किया जाना है यानी विषम घटना आवृत्ति वाले तत्वों का XOR अंतिम परिणाम देगा।
सरणी के प्रत्येक तत्व की उसके सब-एरे में घटना खोजने के लिए, हम इस सूत्र (i+1)*(n-i) का उपयोग करेंगे।
इस सूत्र का उपयोग करके, हम प्रत्येक तत्व की घटना की आवृत्ति ढूंढेंगे और फिर उन तत्वों पर विचार करेंगे जिनकी विषम आवृत्ति है, उन्हें XOR करके अंतिम परिणाम प्राप्त करेंगे।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम,
#include <iostream>
using namespace std;
int xorSubarrayXors(int arr[], int N) {
int result = 0;
for (int i = 0; i < N; i++) {
int frequency = (i + 1) * (N - i);
if (frequency % 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
