Common Divisors

Given an array of n positive integers. Find two integers such that their greatest common divisor is as large as possible.

Example:

Input:  n = 5, arr = {3, 14, 15, 7, 9}
Output: 7

Approach

Java

public class CommonDivisors {
    public static void main(String[] args) {

        int n = 5;

        int[] arr = { 3, 14, 15, 7, 9 };

        commonDivisors(n, arr);

    }

    static int MAXN = (int) (1e6 + 1);

    static void commonDivisors(int n, int[] arr) {

        int[] cnt = new int[MAXN];
        for (int i = 0; i < n; i++) {
            int x = arr[i];

            cnt[x]++;
        }
        for (int i = MAXN - 1; i >= 0; i--) {
            int cur = 0;
            for (int j = i; j < MAXN; j += i)
                cur += cnt[j];
            if (cur > 1) {
                System.out.println(i);
                return;
            }
        }
    }

}

C++

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 1;

void commonDivisors(int n, vector<int> &arr)
{

    vector<int> cnt(MAXN);
    for (int i = 0; i < n; i++)
    {
        int x = arr[i];

        cnt[x]++;
    }
    for (int i = MAXN - 1; i >= 0; i--)
    {
        int cur = 0;
        for (int j = i; j < MAXN; j += i)
            cur += cnt[j];
        if (cur > 1)
        {
            cout << i << "\n";
            return;
        }
    }
}

int main()
{
    int n = 5;

    vector<int> arr = {3, 14, 15, 7, 9};

    commonDivisors(n, arr);

    return 0;
}