সমস্যা বিবৃতি
আমরা n উপাদানের একটি অ্যারে দেওয়া হয়. কাজটি হল পুরো অ্যারের 0 এর XOR তৈরি করা। এটি অর্জন করতে আমরা নিম্নলিখিতগুলি করতে পারি।
আমরা যে কোনো একটি উপাদান নির্বাচন করতে পারি −
- উপাদান নির্বাচন করার পরে, আমরা এটিকে 1 দ্বারা বৃদ্ধি বা হ্রাস করতে পারি।
- পুরো অ্যারের XOR যোগফলকে শূন্য করার জন্য নির্বাচিত উপাদানটির জন্য প্রয়োজনীয় ন্যূনতম সংখ্যা বৃদ্ধি/কমানোর অপারেশন আমাদের খুঁজে বের করতে হবে
উদাহরণ
যদি arr[] ={2, 4, 7} হয় তাহলে 1টি অপারেশন প্রয়োজন −
- উপাদান 2 নির্বাচন করুন
- এটি 1 দ্বারা হ্রাস করুন
- এখন অ্যারে হল {3, 4, 7} এবং এর XOR হল 0
অ্যালগরিদম
- পুরো অ্যারের XOR খুঁজুন
- এখন, ধরুন আমরা arr[i] উপাদান নির্বাচন করেছি, তাই সেই উপাদানটির জন্য প্রয়োজনীয় খরচ হবে পরম(arr[i]-(XORsum^arr[i]))
- প্রতিটি উপাদানের জন্য এই পরম মানগুলির ন্যূনতম গণনা করা আমাদের ন্যূনতম প্রয়োজনীয় অপারেশন হবে
উদাহরণ
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getMinCost(int *arr, int n) {
int operations = INT_MAX;
int elem;
int xorValue = 0;
for (int i = 0; i < n; ++i) {
xorValue = xorValue ^ arr[i];
}
for (int i = 0; i < n; ++i) {
if (operations > abs((xorValue ^ arr[i]) - arr[i])) {
operations = abs((xorValue ^ arr[i]) - arr[i]);
elem = arr[i];
}
}
cout << "Element= " << elem << endl;
cout << "Minimum required operations = " << abs(operations) << endl;
}
int main() {
int arr[] = {2, 4, 7};
int n = sizeof(arr) / sizeof(arr[0]);
getMinCost(arr, n);
return 0;
} আউটপুট
যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট তৈরি করে:
Element = 2 Minimum required operations = 1
