এই সমস্যায়, আমাদেরকে n পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে।
আমাদের কাজ হল পূর্ণসংখ্যা খুঁজে বের করা যা অ্যারের সর্বাধিক সংখ্যক উপাদানকে ভাগ করে।
সমস্যা বর্ণনা: আমাদের একটি সংখ্যা p খুঁজে বের করতে হবে যা অ্যারের সর্বাধিক সংখ্যক উপাদানকে ভাগ করতে পারে। যদি, এরকম একাধিক উপাদান থাকে তাহলে আমরা ছোটটিকে ফিরিয়ে দেব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: arr[] ={4, 5, 6, 7, 8}
আউটপুট: 2
ব্যাখ্যা:
উপাদান 2 ভাগ করে {4, 6, 8}।
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল অ্যারের মাধ্যমে লুপ করা এবং তারপর অ্যারের প্রতিটি উপাদানের জন্য, অ্যারের প্রতিটি উপাদানকে 1 থেকে k থেকে উপাদান দিয়ে ভাগ করুন। এবং অ্যারের সর্বাধিক সংখ্যক উপাদানকে ভাগ করে এমন উপাদানটি ফেরত দিন।
অন্য পদ্ধতি সমস্যা সমাধানের জন্য অ্যারের সমস্ত উপাদান প্রাইম ফ্যাক্টর দ্বারা বিভক্ত করা হয় তা ব্যবহার করে।
আমরা প্রতিটি মৌলিক সংখ্যা দ্বারা বিভাজনের ফ্রিকোয়েন্সি সংরক্ষণ করব এবং তারপর সর্বাধিক কম্পাঙ্ক সহ গুণক ফেরত দেব। আমরা মৌলিক সংখ্যা এবং তাদের ফ্রিকোয়েন্সি একটি হ্যাশে সংরক্ষণ করি।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
int primes[MAXN];
void findPrimeSieve()
{
primes[1] = 1;
for (int i = 2; i < MAXN; i++)
primes[i] = i;
for (int i = 4; i < MAXN; i += 2)
primes[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (primes[i] == i) {
for (int j = i * i; j < MAXN; j += i)
if (primes[j] == j)
primes[j] = i;
}
}
}
vector<int> findFactors(int num)
{
vector<int> factors;
while (num != 1) {
int temp = primes[num];
factors.push_back(temp);
while (num % temp == 0)
num = num / temp;
}
return factors;
}
int findmaxDivElement(int arr[], int n) {
findPrimeSieve();
map<int, int> factorFreq;
for (int i = 0; i < n; ++i) {
vector<int> p = findFactors(arr[i]);
for (int i = 0; i < p.size(); i++)
factorFreq[p[i]]++;
}
int cnt = 0, ans = 1e+7;
for (auto itr : factorFreq) {
if (itr.second >= cnt) {
cnt = itr.second;
ans > itr.first ? ans = itr.first : ans = ans;
}
}
return ans;
}
int main() {
int arr[] = { 4, 5, 6, 7, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The number that divides the maximum elements of the array is "<<findmaxDivElement(arr, n);
return 0;
} আউটপুট
The number that divides the maximum elements of the array is 2
