এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যা n সংখ্যক উপাদান ধারণ করে। আমাদের কাজ হল অ্যারটির সমস্ত সাবঅ্যারের XOR-এর যোগফল নির্ণয় করার জন্য একটি প্রোগ্রাম তৈরি করা।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট: arr[] = {5, 1, 4}
আউটপুট: ১৯
ব্যাখ্যা:
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5,1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
যোগফল = 5 + 1 + 4 + 4 + 5 + 0 = ১৯
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল নেস্টেড লুপ ব্যবহার করে সকল সাবঅ্যারে খুঁজে বের করা এবং তারপর প্রতিটি সাবঅ্যারের উপাদানগুলোর XOR নির্ণয় করে যোগফলে যোগ করা।
এই পদ্ধতিটি কার্যকর নয় কারণ নেস্টেড লুপ ব্যবহার করার কারণে এর টাইম কমপ্লেক্সিটি এক্সপোনেনশিয়াল হয়।
দক্ষ পদ্ধতি: প্রিফিক্স অ্যারে ব্যবহার
একটি দক্ষ পদ্ধতি হল প্রিফিক্স অ্যারে ব্যবহার করা। এই প্রিফিক্স অ্যারে ইনডেক্স i পর্যন্ত সকল উপাদানের XOR সংরক্ষণ করে:
prefixarr[i] = arr[0] ^ arr[1] ^ … ^ arr[i]
এরপর একটি সহজ ফর্মুলা ব্যবহার করে ইনডেক্স i থেকে j পর্যন্ত উপাদানগুলোর XOR বের করা যায়:
XOR(i-j) = prefixarr[j] ^ prefixarr[i-1] (i > 0 এর জন্য) যদি i = 0 হয়, XOR(i-j) = prefixarr[j]
এই ফর্মুলা ব্যবহার করে সকল সাবঅ্যারের XOR নির্ণয় করা সম্ভব।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
int calcSubArrayXORSum(int arr[], int n) {
int sum = 0;
int multiplier = 1;
for (int i = 0; i < 30; i++) {
int oddCount = 0;
bool isOdd = 0;
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
isOdd = (!isOdd);
if (isOdd)
oddCount++;
}
for (int j = 0; j < n; j++) {
sum += (multiplier * oddCount);
if ((arr[j] & (1 << i)) > 0)
oddCount = (n - j - oddCount);
}
multiplier *= 2;
}
return sum;
}
int main() {
int arr[] = { 3, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of XOR of all subarrays is " << calcSubArrayXORSum(arr, n);
return 0;
}
আউটপুট
Sum of XOR of all subarrays is 46
