หา Pair ที่มี GCD สูงสุดใน Array ใน C++

สมมติมี Array ของ Positive Integers ต้องการหา Pair ที่มี GCD สูงสุด ตัวอย่าง A = {1, 2, 3, 4, 5} Output = 2 Pair (2, 4) มี GCD = 2 สูงสุด

วิธีแก้: สร้าง Count Array เก็บจำนวน Divisors ของแต่ละ Element การนับ Divisors ใช้เวลา O(sqrt(arr[i])) หลัง Traversal ครบ ให้ตรวจสอบ Count Array จากท้ายมาหน้า ถ้าเจอค่าที่ > 1 แสดงว่าเป็น Divisor ของ 2 Elements และเป็น Max GCD

ตัวอย่างโค้ด C++

#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 };
    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