এই সমস্যায়, আমাদের 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) .
এই সূত্রটি ব্যবহার করে, আমরা প্রতিটি উপাদানের সংঘটনের ফ্রিকোয়েন্সি খুঁজে বের করব এবং তারপরে চূড়ান্ত ফলাফল পেতে বিজোড় ফ্রিকোয়েন্সি আছে এমন উপাদানগুলিকে বিবেচনা করব।
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
নেমস্পেস std ব্যবহার করে#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
