Given an array of integers find the pair in the array with maximum GCD. Find the maximum possible GCD.
Example 1:
Input: N = 5, a[] = {1, 2, 3, 4, 5}
Output: 2
Explanation: Maximum gcd is GCD(2, 4)
= 2.
Ã¢â¬â¹Example 2:
Input: N = 3, a[] = {3, 5, 2}
Output: 1
Explanation: Maximum gcd is 1.
Your Task:  
Your task is to complete the function MaxGcd() which takes the N and list of N elements as inputs and returns the answer.
Expected Time Complexity: O(N * log N)
Expected Auxiliary Space: O(max(a_{i}))
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ a_{i} ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution:
    def MaxGcd (self, n, a):
        #complete the function here

Solutions:
class Solution:

	def MaxGcd(self, n, a):
		maxi = max(a)
		freq = [0] * (maxi + 1)
		for x in a:
			freq[x] += 1
		for i in range(maxi, 0, -1):
			cnt = 0
			for j in range(i, maxi + 1, i):
				cnt += freq[j]
			if cnt >= 2:
				return i


from collections import Counter
from math import gcd

class Solution:

	def MaxGcd(self, n, a):
		m = max(a)
		a = Counter(a)
		ans = 1
		for i in range(2, m + 1):
			if i <= ans:
				continue
			try:
				r = next((j for j in range(m // i * i, i - 1, -i) if j in a))
				if a[r] > 1:
					ans = r
					continue
				l = next((j for j in range(r - i, i - 1, -i) if j in a))
				ans = gcd(l, r)
			except:
				pass
		return ans


import math

class Solution:

	def MaxGcd(self, n, a):
		high = max(a)
		count = [0] * (high + 1)
		for i in range(0, n):
			count[a[i]] += 1
		counter = 0
		for i in range(high, 0, -1):
			j = i
			while j <= high:
				if count[j] > 0:
					counter += count[j]
				j += i
				if counter >= 2:
					return i
			counter = 0


class Solution:

	def MaxGcd(self, n, arr):
		maxi = max(arr)
		GCD = [-1] * (maxi + 1)
		arr.sort()
		Max_GCD = 0
		for i in range(1, n):
			if arr[i - 1] == arr[i]:
				Max_GCD = arr[i]
		for i in range(n):
			GCD[arr[i]] = 1
		for i in range(n):
			for j in range(arr[i] + arr[i], maxi + 1, arr[i]):
				if GCD[j] != -1:
					GCD[j] = arr[i]
		ans = max(GCD)
		Max_GCD = max(Max_GCD, ans)
		return Max_GCD