সমস্যা বিবরণ
n এলিমেন্টের একটি অ্যারে দেওয়া আছে যাতে এলিমেন্ট গুলো রিপিট হতে পারে। আমরা অ্যারে থেকে যেকোনো সংখ্যক এলিমেন্ট ডিলিট করতে পারি। কাজটি হল অ্যারেকে সমান করার জন্য ন্যূনতম কতগুলো এলিমেন্ট ডিলিট করতে হবে তা বের করা।
arr[] = {10, 8, 10, 7, 10, -1, -4, 12}
আমাদের হাইলাইট করা ৫টি এলিমেন্ট ডিলিট করতে হবে সব অ্যারে এলিমেন্ট একই করার জন্য।
অ্যালগরিদম
1. প্রতিটি এলিমেন্টের ফ্রিকোয়েন্সি কাউন্ট করো 2. ফ্রিকোয়েন্সি গুলোর মধ্যে সর্বোচ্চ ফ্রিকোয়েন্সি বের করো। এটাকে maxFrequency বলব। 3. ডিলিট করতে হবে: n - maxFrequency যেখানে n হল অ্যারে সাইজ
উদাহরণ (C++ কোড)
#include <iostream>
#include <unordered_map>
#include <climits>
#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
using namespace std;
int minDeleteOperations(int *arr, int n) {
unordered_map<int, int> frequency;
int maxFrequency = INT_MIN;
for (int i = 0; i < n; ++i) {
frequency[arr[i]]++;
}
for (auto it = frequency.begin(); it != frequency.end(); ++it) {
maxFrequency = max(maxFrequency, it->second);
}
return (n - maxFrequency);
}
int main() {
int arr[] = {10, 8, 10, 7, 10, -1, 9, 4};
cout << "Required deletes: " << minDeleteOperations(arr, SIZE(arr)) << "\n";
return 0;
}
আউটপুট
Required deletes: 5
