ধারণা
অ-ঋণাত্মক পূর্ণসংখ্যাগুলির প্রদত্ত অ্যারের Arr[] এর ক্ষেত্রে, কাজটি হল একটি পূর্ণসংখ্যা X নির্ধারণ করা যাতে (Arr[0] XOR X) + (Arr[1] XOR X) + … + Arr[n – 1] XOR X ন্যূনতম সম্ভব।
ইনপুট
Arr[] = {3, 4, 5, 6, 7} আউটপুট
X = 7, Sum = 10
পন্থা
তাই আমরা বাইনারি উপস্থাপনায় অ্যারের প্রতিটি সংখ্যার 'i'th বিট যাচাই করব এবং সেই সংখ্যাগুলি বিবেচনা করব এবং গণনা করব যেখানে সেই 'i’th বিটটি '1' এ সেট করা আছে কারণ এই সেট বিটগুলি ন্যূনতম করার পরিবর্তে যোগফলকে সর্বাধিক করতে অবদান রাখবে। এর ফলস্বরূপ, আমাদের এই সেটটি 'i'th বিট থেকে '0' তৈরি করতে হবে যদি গণনা N/2-এর থেকে বেশি হয় এবং গণনা N/2-এর থেকে কম হয় তবে 'i'th বিট সেট থাকা সংখ্যাগুলি কম হয়। এবং এর ফলে এটি উত্তরকে প্রভাবিত করবে না। আমরা জানি দুটি বিটের XOR অপারেশন অনুসারে, যখন A XOR B এবং A এবং B উভয়ই একই হয় তখন এটি '0' হিসাবে ফলাফল প্রদান করে তাই আমরা সেই 'i'th বিটটিকে আমাদের সংখ্যা (সংখ্যা) থেকে '1'-এ তৈরি করব, এর ফলে (1 XOR 1) '0' দেবে এবং যোগফল কমিয়ে দেবে।
উদাহরণ
// C++ implementation of the approach
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
void findX1(int arr1[], int n1){
int* itr1 = max_element(arr1, arr1 + n1);
int p1 = log2(*itr1) + 1;
int X1 = 0;
for (int i = 0; i < p1; i++) {
int count1 = 0;
for (int j = 0; j < n1; j++) {
if (arr1[j] & (1 << i)) {
count1++;
}
}
if (count1 > (n1 / 2)) {
X1 += 1 << i;
}
}
long long int sum1 = 0;
for (int i = 0; i < n1; i++)
sum1 += (X1 ^ arr1[i]);
cout << "X = " << X1 << ", Sum = " << sum1;
}
// Driver code
int main(){
int arr1[] = { 3, 4, 5, 6, 7 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
findX1(arr1, n1);
return 0;
} আউটপুট
X = 7, Sum = 10
