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

এই সমস্যায় আমাদের একটি অ্যারে arr[] দেওয়া আছে সাইজ 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 ক্যালকুলেট করা।

আলগরিদম:

Initialise XorSum = 0

Step 1: 0 থেকে n পর্যন্ত ইটারেট করুন। ফলো করুন:

Step 1.1: 0 থেকে n পর্যন্ত ইটারেট করুন। ফলো করুন

Step 1.1.1: Update XorSum i.e. XorSum = XorSum ^ (arr[i]+arr[j]).

Step 2: sum রিটার্ন করুন

আমাদের কোডের কাজ দেখানোর প্রোগ্রাম

উদাহরণ

#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²-এর ক্রমে।

একটি দক্ষ সমাধান হলো XOR-এর গুণধর্ম ব্যবহার করা। সমস্যা সমাধানের জন্য, আমরা অ্যারের সব উপাদানের XOR বের করব এবং তারপর সেটিকে দুই গুণ করব।

আলগরিদম:

Initialize XorSum = 0

Step 1: 0 থেকে n পর্যন্ত ইটারেট করুন।

Step 1.1: update XorSum i.e. XorSum = XorSum ^ arr[i]

Step 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