এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল একটি অ্যারেতে সমস্ত জোড়ার যোগফলের XOR-এর যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেখা যাক,
ইনপুট: arr[5, 7, 9]
আউটপুট: 22
ব্যাখ্যা:
(5+5) ^ (5+7) ^ (5+9) ^ (7+5) ^ (7+7) ^ (7+9) ^ (9+5) ^ (9+7) ^ (9+9) =22
একটি নেস্টেড লুপ ব্যবহার করে সমস্যার একটি সহজ সমাধান। এবং অ্যারে থেকে সমস্ত সম্ভাব্য জোড়া তৈরি করা। এবং প্রতিটি জোড়ার যোগফলের XOR গণনা করুন।
অ্যালগরিদম:
শুরু করুন XorSum =0
ধাপ 1: 0 থেকে n পর্যন্ত পুনরাবৃত্তি করুন। অনুসরণ করুন:
ধাপ 1.1: 0 থেকে n পর্যন্ত পুনরাবৃত্তি করুন। অনুসরণ করুন
ধাপ 1.1.1: XorSum আপডেট করুন যেমন XorSum =XorSum ^ (arr[i]+arr[j])।
ধাপ 2: ফেরত যোগফল
আমাদের কোডের কাজ চিত্রিত করার জন্য প্রোগ্রাম
উদাহরণ
#include <iostream>
using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
XorSum = XorSum^(arr[i]+arr[j]);
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"XOR of sum of all pairs in an array is "<<findSumXORPair(arr, n);
return 0;
} আউটপুট
XOR of sum of all pairs in an array is 22
এই সমাধানটি কার্যকর নয় কারণ এর সময় জটিলতা n 2 ক্রম অনুসারে .
একটি দক্ষ সমাধান হল XOR এর বৈশিষ্ট্যগুলি ব্যবহার করা। সমস্যা সমাধানের জন্য, আমরা অ্যারের সমস্ত উপাদানের XOR গণনা করব এবং তারপর এটিকে দুই দ্বারা গুণ করব।
অ্যালগরিদম:
XorSum =0
শুরু করুনধাপ 1: 0 থেকে n পর্যন্ত পুনরাবৃত্তি করুন।
ধাপ 1.1: XorSum আপডেট করুন অর্থাৎ XorSum =XorSum ^ arr[i]
ধাপ 2: যোগফল দ্বিগুণ করে ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
XorSum = XorSum^arr[i];
XorSum = 2*XorSum;
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"XOR of sum of all pairs in an array is "<<findSumXORPair(arr, n);
return 0;
} আউটপুট
XOR of sum of all pairs in an array is 22
