সমস্যা বিবরণ
একটি অ্যারে "arr" দেওয়া আছে। অ্যারেটি 'ভালো' (good) করার জন্য ন্যূনতম কতগুলো এলিমেন্ট অপসারণ করতে হবে তা বের করতে হবে।
একটি সিকোয়েন্স a1, a2, a3...an 'ভালো' कहলাবে যদি প্রতিটি a[i]-র জন্য একটি a[j] (i ≠ j) وجود করে যাতে a[i] + a[j] ২-এর ঘাত হয়।
arr1[] = {1, 1, 7, 1, 5}
উপরের অ্যারেতে '5' ডিলিট করলে অ্যারেটি 'ভালো' হয়। এরপর যেকোনো arr[i] + arr[j] ২-এর ঘাত হবে:
- arr[0] + arr[1] = (1 + 1) = 2 যা ২-এর ঘাত
- arr[0] + arr[2] = (1 + 7) = 8 যা ২-এর ঘাত
এলগরিদম
1. শুধু সেই a[i] ডিলিট করতে হবে যার জন্য কোনো a[j] নেই যাতে a[i] + a[j] ২-এর ঘাত হয়। 2. প্রতিটি ভ্যালুর ঘটনার সংখ্যা গণনা করুন। 3. চেক করুন a[i]-র কোনো জোড়া a[j] আছে কিনা।
উদাহরণ কোড
#include <iostream>
#include <map>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minDeleteRequred(int *arr, int n) {
map<int, int> frequency;
for (int i = 0; i < n; ++i) {
frequency[arr[i]]++;
}
int delCnt = 0;
for (int i = 0; i < n; ++i) {
bool doNotRemove = false;
for (int j = 0; j < 31; ++j) {
int pair = (1 << j) - arr[i];
if (frequency.count(pair) &&
(frequency[pair] > 1 ||
(frequency[pair] == 1 && pair != arr[i]))) {
doNotRemove = true;
break;
}
}
if (!doNotRemove) {
++delCnt;
}
}
return delCnt;
}
int main() {
int arr[] = {1, 1, 7, 1, 5};
cout << "Minimum elements to be deleted = " << minDeleteRequred(arr, SIZE(arr)) << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Minimum elements to be deleted = 1
