এই সমস্যায়, আমাদেরকে n পূর্ণসংখ্যার একটি অ্যারে [] দেওয়া হয়েছে। আমাদের কাজ হল একটি অ্যারের সমস্ত জোড়ার XOR-এর যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input: arr[] = {5, 1, 4}
Output: 10
Explanation: the sum of all pairs:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
sum = 4 + 5 + 1 = 10 এই সমস্যাটি সমাধান করার জন্য একটি সহজ পদ্ধতি হল নেস্টেড লুপ চালানো এবং সমস্ত জোড়া সংখ্যা খুঁজে বের করা। প্রতিটি জোড়ার XOR খুঁজুন এবং যোগফল যোগ করুন।
অ্যালগরিদম
Initialise sum = 0 Step 1: for(i -> 0 to n). Do: Step 1.1: for( j -> i to n ). Do: Step 1.1.1: update sum. i.e. sum += arr[i] ^ arr[j]. Step 2: return sum.
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int findXORSum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
sum += (arr[i]^arr[j]);
return sum;
}
int main() {
int arr[] = { 5, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all pairs in an array is "<<findXORSum(arr, n);
return 0;
} আউটপুট
Sum of XOR of all pairs in an array is 10
অ্যালগরিদমের সময় জটিলতা হল O(n2) এবং এটি সমস্যার সবচেয়ে কার্যকর সমাধান নয়৷
সমস্যার একটি দক্ষ সমাধান হল বিট ম্যানিপুলেশন কৌশল ব্যবহার করা।
এখানে, আমরা সংখ্যার বিট এবং প্রতিটি অবস্থান বিবেচনা করব। এবং নীচের সূত্রটি প্রয়োগ করুন মধ্যবর্তী সমষ্টি খুঁজুন,
(number of set bits) * (number of unset bits) * (2^(bit_position))
চূড়ান্ত যোগফল খুঁজে পেতে, আমরা সমস্ত বিটের মধ্যবর্তী যোগফল যোগ করব।
আমাদের সমাধান হল 64-বিট পূর্ণসংখ্যা মানের জন্য। এই পদ্ধতির জন্য, আমাদের বিটের সংখ্যা প্রয়োজন।
অ্যালগরিদম
Initialize sum = 0, setBits = 0, unsetBits = 0. Step 1: Loop for i -> 0 to 64. repeat steps 2, 3. Step 2: Reset setBits and unsetBits to 0. Step 3: For each element of the array find the value of setBits and unsetBits. At ith position. Step 4: update sum += (setBits * unsetBits * (2i))
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
#include <math.h>
using namespace std;
long findXORSum(int arr[], int n) {
long sum = 0;
int unsetBits = 0, setBits = 0;
for (int i = 0; i < 32; i++) {
unsetBits = 0; setBits = 0;
for (int j = 0; j < n; j++) {
if (arr[j] % 2 == 0)
unsetBits++;
else
setBits++;
arr[j] /= 2;
}
sum += ( unsetBits*setBits* (pow(2,i)) );
}
return sum;
}
int main() {
int arr[] = { 5, 1, 4, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all pairs in an array is "<<findXORSum(arr, n);
return 0;
} আউটপুট
Sum of XOR of all pairs in an array is 68
