সমস্যা বিবরণ
n এলিমেন্টের একটি অ্যারে দেওয়া আছে। টাস্ক হলো পুরো অ্যারে-এর XOR ০ করা। এজন্য আমরা নিচের কাজগুলো করতে পারি:
আমরা যেকোনো একটি এলিমেন্ট সিলেক্ট করতে পারি −
- এলিমেন্ট সিলেক্ট করার পর, সেটি ১ দিয়ে ইনক্রিমেন্ট বা ডিক্রিমেন্ট করতে পারি।
- সিলেক্ট করা এলিমেন্টের জন্য মিনিমাম সংখ্যক ইনক্রিমেন্ট/ডিক্রিমেন্ট অপারেশন বের করতে হবে যাতে পুরো অ্যারে-এর XOR সম ০ হয়।
উদাহরণ
যদি arr[] = {2, 4, 7} হয়, তবে ১ অপারেশন দরকার −
- এলিমেন্ট ২ সিলেক্ট করুন
- ১ দিয়ে ডিক্রিমেন্ট করুন
- এখন অ্যারে হয়ে যায় {3, 4, 7} এবং এর XOR হলো ০
অ্যালগরিদম
- পুরো অ্যারে-এর XOR বের করুন
- মান लें, আমরা arr[i] এলিমেন্টটি সিলেক্ট করেছি, তাহলে সেটির কস্ট হবে absolute(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
