CODEWITHSUNDEEP
algorithmdata-structures
Rajat kashyap
Rajat kashyap

Reputation: 622

How to find the pair in an array which have maximum gcd

I have to find the the pair in an array which have maximum GCD. I tried different approach but all those solution doesn't run in time, time limit exceed in every solution.

So is there any efficient method to do so.

example =>

Input : arr[] : { 1 2 3 4 5 }
Output : 2

Explanation : Pair {2, 4} has GCD 2 which is highest. Other pairs have a GCD of 1.

I tried these solutions =>

All above mentioned solution doesn't work.

The link to the question is
https://practice.geeksforgeeks.org/problems/maximum-gcd-pair3534/1

Upvotes: 0

Views: 1852

Answers (1)

starboy_jb
starboy_jb

Reputation: 935

We can use the same logic, divisor occurrence but with a simple optimization. Instead of calculating divisor for each number separately. We will calculate divisors collectively and calculate the answer accordingly. We will traverse each number and then it all multiple till max_element and will keep track of the number of elements for which the current number is the divisor and if the occurrence is greater than 1 we will update our answer. So the solution will be,

int MaxGcd(int n, int a[]) { 
        
    int mx = *max_element(a, a + n);
    
    vector<int> cnt(mx + 1, 0);
    vector<int> occurrence(mx + 1, 0);
    
    for (int i = 0; i < n; i++) {
        occurrence[a[i]]++;
    }
    
    int ans = 1;
    
    for (int i = 2; i <= mx; i++) {
        for (int j = i; j <= mx; j += i) {
            cnt[i] += occurrence[j];
            if (cnt[i] > 1) {
                ans = i;
            }
        }
    }
    
    return ans;
}

Upvotes: 1

Related Questions