সমস্যা বিবরণ
একটি পূর্ণসংখ্যার অ্যারে arr দেওয়া আছে। অ্যারের সব এলিমেন্ট ডিলিট করতে ন্যূনতম কতগুলো অপারেশন দরকার তা প্রিন্ট করতে হবে। ডিলিট করার সময় নিচের সীমাবদ্ধতা মেনে চলতে হবে:
- অ্যারে থেকে যেকোনো এলিমেন্ট যাদবিপরীতভাবে বেছে নেওয়া যাবে এবং তার দ্বারা বিভাজ্য সব এলিমেন্ট অ্যারे থেকে মুছে ফেলা যাবে।
যদি arr[] = {2, 4, 15, 10, 8, 5, 3} হয়, তবে ৩টি অপারেশন দরকার:
- ২ বেছে নিলে মুছে যাবে {2, 4, 10, 8}
- ৫ বেছে নিলে মুছে যাবে {5, 15}
- ৩ বেছে নিলে মুছে যাবে {3}
এলগরিদম
1. অ্যারেটি আর্ধবক্রমে সর্ট করুন এবং প্রতিটি এলিমেন্টের ঘটনার সংখ্যা গণনা করুন 2. শুরু থেকে প্রতিটি অचিহ্নিত এলিমেন্টের জন্য, তার দ্বারা বিভাজ্য সব এলিমেন্ট চিহ্নিত করুন এবং রেজাল্ট কাউন্টার বাড়ান
উদাহরণ কোড
#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define MAX 100
using namespace std;
int getMinOperations(int *arr, int n) {
int map[MAX] = {0};
sort(arr, arr + n);
for (int i = 0; i < n; ++i) {
map[arr[i]]++;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (map[arr[i]]) {
for (int j = i; j < n; ++j) {
if (arr[j] % arr[i] == 0) {
map[arr[j]] = 0;
}
}
++cnt;
}
}
return cnt;
}
int main() {
int arr[] = {2, 4, 15, 10, 8, 5, 3};
cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Minimum required operations = 3
