সমস্যা বিবরণ
n পজিটিভ ইন্টিজারের একটি অ্যারে দেওয়া আছে। সব এলিমেন্ট সমান করার জন্য ন্যূনতম অপারেশন সংখ্যা বের করতে হবে। অ্যারে এলিমেন্টে যেকোনো এলিমেন্ট দিয়ে যোগ, গুণ, বিয়োগ বা ভাগ করা যায়।
উদাহরণ
ইনপুট অ্যারে = {1, 2, 3, 4} হলে ন্যূনতম ৩ অপারেশন দরকার। উদাহরণস্বরূপ, ৩টি যোগ করে সব এলিমেন্ট ৪ করা যায়।
অ্যালগরিদম
1. সর্বোচ্চ ফ্রিকোয়েন্সি বালা এলিমেন্ট সিলেক্ট করুন। সেটাকে 'x' বলুন। 2. এখন n-x অপারেশন করতে হবে কারণ x সংখ্যক এলিমেন্ট একই ভ্যালুর।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinOperations(int *arr, int n) {
unordered_map hash;
for (int i = 0; i < n; ++i) {
hash[arr[i]]++;
}
int maxFrequency = 0;
for (auto elem : hash) {
if (elem.second > maxFrequency) {
maxFrequency = elem.second;
}
}
return (n - maxFrequency);
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum required operations = " << getMinOperations(arr, n) << endl;
return 0;
}
উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট জেনারেট হবে
আউটপুট
Minimum required operations = 3
