पूर्णांक खोजें जो सी ++ में सरणी के तत्वों की अधिकतम संख्या को विभाजित करता है

इस समस्या में, हमें n पूर्णांकों का एक सरणी arr[] दिया जाता है।

हमारा काम है उन पूर्णांकों को खोजना जो सरणी के तत्वों की अधिकतम संख्या को विभाजित करते हैं।

समस्या का विवरण: हमें एक संख्या p खोजने की आवश्यकता है जो सरणी के तत्वों की अधिकतम संख्या को विभाजित कर सके। यदि ऐसे एक से अधिक तत्व हैं तो हम छोटे वाले को वापस कर देंगे।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट: गिरफ्तारी [] ={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