এই সমস্যায়, আমাদেরকে n সংখ্যার একটি অ্যারে [] দেওয়া হয়েছে। আমাদের কাজ হল সমস্ত সম্ভাব্য উপসেটের XOR-এর যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
এখানে, আমরা অ্যারের সমস্ত উপসেট খুঁজে পাব। তারপর প্রতিটি উপসেটের জন্য, আমরা উপসেটের উপাদানগুলির XOR খুঁজে বের করব এবং তাদের যোগফল পরিবর্তনশীলে যোগ করব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input: arr[] = {5, 1, 4}
Output: 20
Explanation: XOR of all subsets:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
Sum of XOR = 5 + 1 + 4 + 4 + 1 + 5 = 20 সমস্যার একটি সহজ সমাধান, লুপ ব্যবহার করা এবং অ্যারের সম্ভাব্য সব উপসেট খুঁজে বের করা এবং তারপর প্রতিটি উপসেটের জন্য সমস্ত উপাদানের XOR খুঁজুন এবং যোগফল আপডেট করুন। শেষে যোগফল ফেরত দিন।
এটি একটি কার্যকর পদ্ধতি নয়, বড় মূল্যের জন্য, সময়ের জটিলতা দ্রুতগতিতে বৃদ্ধি পাবে।
একটি দক্ষ পন্থা হল XOR এর বৈশিষ্ট্যগুলি ব্যবহার করা। এখানে, আমরা অ্যারের সমস্ত উপাদানের OR খুঁজে পাব এবং বিটগুলি পরীক্ষা করব। যদি ith সেট করা থাকে, তাহলে যোগফল (2^(n-1+i)) দিয়ে আপডেট করুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#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);
} আউটপুট
Sum of XOR of all possible subsets is 20
