ধরুন আমাদের ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে আছে। আমাদের কাজ হল অ্যারে থেকে জোড়া পূর্ণসংখ্যা খুঁজে বের করা, যেখানে 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
