इस समस्या में, हमें n पूर्णांकों की एक सरणी arr[] दी गई है।
हमारा कार्य है वह पूर्णांक ढूंढना जो सरणी के अधिकतम तत्वों को विभाजित करता है।
समस्या विवरण: हमें एक संख्या 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
