এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যা n সংখ্যক উপাদান ধারণ করে। আমাদের কাজ হল অ্যারটির সমস্ত সম্ভাব্য সাবসেটের XOR-এর যোগফল নির্ণয় করার জন্য একটি প্রোগ্রাম তৈরি করা।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট: arr[] = {5, 1, 4}
আউটপুট: ২০
ব্যাখ্যা:
সাবসেটের XOR:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
XOR-এর যোগফল = 5 + 1 + 4 + 4 + 1 + 5 = ২০
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল লুপ ব্যবহার করে সকল সম্ভাব্য সাবসেট খুঁজে বের করা এবং প্রতিটি সাবসেটের উপাদানগুলোর XOR নির্ণয় করে যোগফলে যোগ করা।
বড় ইনপুটের জন্য এই পদ্ধতিটি কার্যকর নয় কারণ টাইম কমপ্লেক্সিটি এক্সপোনেনশিয়ালভাবে বেড়ে।
দক্ষ পদ্ধতি: XOR-এর বৈশিষ্ট্য ব্যবহার
একটি দক্ষ পদ্ধতি হল XOR-এর বৈশিষ্ট্য ব্যবহার করা। এখানে আমরা অ্যারের সকল উপাদানের OR নির্ণয় করব এবং বিটগুলো চেক করব। যদি i-তম বিট সেট থাকে, তাহলে যোগফলকে (2^(n-1+i)) দিয়ে আপডেট করব।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
#include <math.h>
using namespace std;
int subSetXORSum(int arr[], int n) {
int bitOR = 0;
for (int i = 0; i < n; ++i)
bitOR |= arr[i];
return (bitOR * pow(2, n - 1));
}
int main() {
int arr[] = {1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of XOR of all possible subsets is " << subSetXORSum(arr, size);
return 0;
}
আউটপুট
Sum of XOR of all possible subsets is 20
