সমস্যা বিবরণ
N ইন্টিজারের একটি অ্যারে arr[] দেওয়া আছে। আমাদের একটি প্রোগ্রাম লিখতে হবে যা বের করবে ন্যূনতম কতগুলো এলিমেন্ট অ্যারে থেকে সরাতে হবে যাতে বাকি এলিমেন্টগুলোর যোগফল জোড় হয়।
উদাহরণ
ইনপুট অ্যারে {10, 20, 30, 5} হলে একটি এলিমেন্ট সরাতে হবে (৫) যাতে অ্যারে সম জোড় হয়।
অ্যালগরিদম
1. যেকোনো সংখ্যক সম সংখ্যার যোগফল সর্বদা সম হয়। 2. বিজোড় সংখ্যক বিজোড় সংখ্যার যোগফল সর্বদা বিজোড় হয়। 3. জোড় সংখ্যক বিজোড় সংখ্যার যোগফল সর্বদা সম হয়। 4. অ্যারেতে বিজোড় এলিমেন্টের সংখ্যা গণনা করুন। যদি বিজোড় এলিমেন্টের সংখ্যা জোড় হয়, তবে অ্যারে থেকে কোনো এলিমেন্ট সরাতে হবে না। কিন্তু যদি বিজোড় এলিমেন্টের সংখ্যা বিজোড় হয়, তবে অ্যারে থেকে যেকোনো একটি বিজোড় এলিমেন্ট সরালে যোগফল জোড় হয়ে যাবে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinRemovals(int *arr, int n) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] % 2 == 1) {
++cnt;
}
}
return (cnt % 2 == 0) ? 0 : 1;
}
int main() {
int arr[] = {10, 20, 30, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum required removals = " << getMinRemovals(arr, n) << endl;
return 0;
}
উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট জেনারেট হবে
আউটপুট
Minimum required removals = 1
