सी++ में एक सरणी में अधिकतम जीसीडी के साथ जोड़ी खोजें

मान लीजिए कि हमारे पास सकारात्मक पूर्णांकों की एक सरणी है। हमारा काम सरणी से पूर्णांकों की जोड़ी को खोजना है, जहां GCD मान अधिकतम है। मान लीजिए A ={1, 2, 3, 4, 5}, तो आउटपुट 2 है। जोड़ी (2, 4) में GCD 2 है, अन्य GCD मान 2 से कम हैं।

इस समस्या को हल करने के लिए, हम प्रत्येक तत्व के भाजक की गिनती को संग्रहीत करने के लिए एक गिनती सरणी बनाए रखेंगे। भाजक गिनने की प्रक्रिया में O(sqrt(arr[i])) समय लगेगा। पूरे ट्रैवर्सल के बाद, हम पिछले इंडेक्स से पहले इंडेक्स तक गिनती सरणी को पार कर सकते हैं, फिर अगर हमें कुछ मान मिलता है जहां तत्व 1 से अधिक है, तो इसका मतलब है कि यह 2 तत्वों का विभाजक है और अधिकतम जीसीडी भी है।

उदाहरण

#include <iostream>
#include <cmath>
using namespace std;
int getMaxGCD(int arr[], int n) {
   int high = 0;
   for (int i = 0; i < n; i++)
   high = max(high, arr[i]);
   int divisors[high + 1] = { 0 }; //array to store all gcd values
   for (int i = 0; i < n; i++) {
      for (int j = 1; j <= sqrt(arr[i]); j++) {
         if (arr[i] % j == 0) {
            divisors[j]++;
         if (j != arr[i] / j)
            divisors[arr[i] / j]++;
         }
      }
   }
   for (int i = high; i >= 1; i--)
   if (divisors[i] > 1)
   return i;
}
int main() {
   int arr[] = { 1, 2, 4, 8, 12 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Max GCD: " << getMaxGCD(arr,n);
}

आउटपुट

Max GCD: 4