मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी है। हमारा कार्य सरणी से पूर्णांकों की जोड़ी ढूंढना है, जहां GCD मान अधिकतम है। मान लीजिए A = {1, 2, 3, 4, 5}, तो आउटपुट 2 है। जोड़ी (2, 4) का GCD 2 है, अन्य GCD मान 2 से कम हैं।
इस समस्या को हल करने के लिए, हम एक काउंट सरणी बनाए रखेंगे जो प्रत्येक तत्व के भाजकों की गिनती संग्रहीत करेगी। भाजकों की गिनती की प्रक्रिया O(sqrt(arr[i])) समय लेगी। संपूर्ण ट्रैवर्सल के बाद, हम काउंट सरणी को अंतिम इंडेक्स से पहले इंडेक्स तक ट्रैवर्स कर सकते हैं, फिर यदि हमें कोई मान मिलता है जहां तत्व 1 से अधिक है, तो इसका मतलब है कि यह 2 तत्वों का भाजक है और अधिकतम GCD भी है।
उदाहरण
#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