C++-এ অ্যারেতে সকল জোড়ার XOR-এর যোগফল

এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যা n সংখ্যক পূর্ণসংখ্যা ধারণ করে। আমাদের কাজ হল অ্যারেতে সকল সম্ভাব্য জোড়ার XOR-এর যোগফল নির্ণয় করার জন্য একটি প্রোগ্রাম তৈরি করা।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট: arr[] = {5, 1, 4}
আউটপুট: ১০
ব্যাখ্যা: 
সকল জোড়ার যোগফল:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
যোগফল = 4 + 5 + 1 = ১০

এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল নেস্টেড লুপ চালিয়ে সকল জোড়া খুঁজে বের করা, প্রতিটি জোড়ার XOR নির্ণয় করা এবং যোগফলে যোগ করা।

আলগরিদম

যোগফল = 0 আপডেট করুন
ধাপ ১: i = 0 থেকে n পর্যন্ত লুপ চালান। করুন:
    ধাপ ১.১: j = i থেকে n পর্যন্ত লুপ চালান। করুন:
        ধাপ ১.১.১: যোগফল আপডেট করুন। অর্থাৎ sum += arr[i] ^ arr[j]।
ধাপ ২: যোগফল ফেরত দিন।

C++ প্রোগ্রাম উদাহরণ (সহজ পদ্ধতি)

#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(n²) যা সবচেয়ে দক্ষ সমাধান নয়।

দক্ষ সমাধান: বিট ম্যানিপুলেশন কৌশল

এখানে আমরা সংখ্যাগুলোর বিট পজিশন বিবেচনা করব এবং নিচের ফর্মুলা ব্যবহার করে ইন্টারমিডিয়েট যোগফল বের করব:

(সেট বিটের সংখ্যা) * (আনসেট বিটের সংখ্যা) * (2^(বিট_পজিশন))

ফাইনাল যোগফল পেতে সকল বিটের ইন্টারমিডিয়েট যোগফল যোগ করতে হবে। আমাদের সমাধান ৩২-বিট ইন্টিজার মান জন্য।

আলগরিদম

যোগফল = 0, সেটবিট = 0, আনসেটবিট = 0 আরম্ভ করুন।
ধাপ ১: i = 0 থেকে ৩১ পর্যন্ত লুপ চালান। ধাপ ২, ৩ পুনরাবৃত্তি করুন।
ধাপ ২: সেটবিট এবং আনসেটবিট ০-তে রিসেট করুন।
ধাপ ৩: অ্যারের প্রতিটি উপাদানের জন্য i-তম পজিশনে সেটবিট এবং আনসেটবিটের মান বের করুন।
ধাপ ৪: যোগফল আপডেট করুন: sum += (setBits * unsetBits * (2^i))

C++ প্রোগ্রাম উদাহরণ (দক্ষ পদ্ধতি)

#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