এই সমস্যায়, আমাদেরকে n সংখ্যার একটি অ্যারে [] দেওয়া হয়েছে। আমাদের কাজ হল অ্যারের সমস্ত সাবয়ারের XOR-এর যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা৷
এখানে, আমাদের প্রদত্ত অ্যারের সমস্ত সাব-অ্যারে খুঁজে বের করতে হবে, এবং তারপর প্রতিটি সাব-অ্যারের জন্য, আমরা উপাদানের xor খুঁজে বের করব এবং যোগফল ভেরিয়েবলে XOR মান যোগ করব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input: arr[] = {5, 1, 4}
Output:
Explanation: XOR of all subarrays for the array :
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
Sum = 5 + 1 + 4 + 4 + 5 + 0 = 19 এই সমস্যাটি সমাধান করার একটি সহজ পদ্ধতি হল নেক্সট ফর লুপ ব্যবহার করে সমস্ত সাবয়ারে খুঁজে বের করা। তারপর সাবয়ারের উপাদানগুলির XOR খুঁজে বের করা এবং যোগফল পরিবর্তনশীল যোগ করা।
এই সমাধানটি কার্যকর নয় কারণ এটি লুপের নেস্টিং ব্যবহার করে এবং সূচকীয় সময়ের জটিলতা থাকবে৷
এই সমস্যাটি সমাধান করার জন্য একটি দক্ষ পদ্ধতি হল প্রিফিক্স অ্যারে ব্যবহার করা। এই প্রিফিক্স অ্যারে i পর্যন্ত অ্যারের সমস্ত উপাদানের xor সংরক্ষণ করবে। অর্থাৎ,
prefixarr[i] = arr[0]^arr[1]^ … ^arr[i].
এর পরে, আমরা সূচক i থেকে j পর্যন্ত উপাদানগুলির XOR খুঁজে বের করার জন্য একটি সহজ সূত্র প্রয়োগ করতে পারি।
XOR(i-j) = prefixarr[j] - prefixarr[i]for i >= 0. If i = 0, XOR(i-j) = prefixarr[j]
এই সূত্রটি ব্যবহার করে আমরা সমস্ত সাবয়ারের XOR খুঁজে পাব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#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
