এই সমস্যায়, আমাদের n উপাদানের একটি অ্যারে দেওয়া আছে। আমাদের কাজ হল অ্যারের উপাদান থেকে তৈরি সব সম্ভাব্য সাবঅ্যারে (ক্রমে নেওয়া) এর XOR-এর 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 করলে ০ হয়। এতে আমরা সাবঅ্যারে লিস্টে জোড় বার আসা সব ভ্যালুকে উপেক্ষা করব, এখন বিজোড় ফ্রিকোয়েন্সি উপস্থিতি वाले এলিমেন্টগুলোকে বিবেচনা করব অর্থাৎ বিজোড় ফ্রিকোয়েন্সি والے এলিমেন্টগুলোর 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
