কoncepশন
অ-নেতিবাচক পূর্ণসংখ্যার একটি অ্যারে Arr[] দেওয়া থাকলে, একটি পূর্ণসংখ্যা X নির্ধারণ করা হয় যাতে (Arr[0] XOR X) + (Arr[1] XOR X) + … + (Arr[n-1] XOR X) এর যোগফল ন্যূনতম হয়।
পদ্ধতি
প্রতিটি সংখ্যার বাইনেরি উপস্থাপনায় 'i'-তম বিট যাচাই করে এবং সেট বিটগুলির গণনা করা হয়। যেহেতু সেট বিটগুলি যোগফলকে সর্বাধিক করার পরিবর্তে ন্যূনতম করতে সাহায্য করে, তাই যদি গণনা N/2-এর চেয়ে বেশি হয়, তবে আমাদের কনস্ট্রাক্ট করা সংখ্যার 'i'-তম বিটকে '0' সেট করতে হবে। আর যদি গণনা N/2-এর চেয়ে কম হয়, তবে সেট বিটযুক্ত সংখ্যাগুলো কম থাকায় এটি উত্তরকে প্রভাবিত করবে না। XOR অপারেশানানুযায়ী, যখন দুটি বিট সমান (A XOR B, যেখানে A=B), ফলাফল '0' হয়। তাই আমরা কনস্ট্রাক্ট করা সংখ্যার 'i'-তম বিটকে '1' সেট করি, যাতে (1 XOR 1) = '0' হয় এবং যোগফল ন্যূনতম হয়।
উদাহরণ
// C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
void findX(int arr[], int n) {
int* itr = max_element(arr, arr + n);
int p = log2(*itr) + 1;
int X = 0;
for (int i = 0; i < p; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[j] & (1 << i))
count++;
}
if (count > (n / 2))
X += (1 << i);
}
long long sum = 0;
for (int i = 0; i < n; i++)
sum += (X ^ arr[i]);
cout << "X = " << X << ", Sum = " << sum;
}
int main() {
int arr[] = {3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
findX(arr, n);
return 0;
}
আউটপুট
X = 7, Sum = 10
