ধরুন আমাদের একটি পজিটিভ ইন্টিজার অ্যারে আছে। আমাদের টাস্ক হলো অ্যারে থেকে দুটি ইন্টিজারের পেয়ার বের করা যাদের GCD মান সর্বোচ্চ। ধরুন A = {1, 2, 3, 4, 5}, তবে আউটপুট ২। পেয়ার (2, 4)-এর GCD ২, অন্যান্য GCD মান ২-এর চেয়ে কম।
এই সমস্যাটি সমাধান করতে আমরা একটি কাউন্ট অ্যারে মেইনটেইন করব যা প্রতিটি উপাদানের ডিভাইজরের কাউন্ট স্টোর করবে। ডিভাইজর কাউন্ট করার প্রসেস O(sqrt(arr[i])) টাইম নেবে। পুরো ট্রাভার্সালের পর, কাউন্ট অ্যারেটি লাস্ট ইন্ডেক্স থেকে ফার্স্ট ইন্ডেক্স পর্যন্ত ট্রাভার্স করব, এবং যদি কোনো ভ্যালু পাওয়া যায় যেটি ১-এর চেয়ে বড়, তবে সেটি ২টি উপাদানের ডিভাইজর এবং সর্বোচ্চ 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
