Given an array A of N elements. The task is to find the greatest number S such that it is product of two elements of given array (S cannot be included in pair. Also, pair must be from different indices). 
Example 1:
Input :  arr[] = {10, 3, 5, 30, 35}
Output:  30
Explanation: 30 is the product of 10 and 3.
Example 2:
Input :  arr[] = {2, 5, 7, 8}
Output:  -1
Explanation: Since, no such element exists.
Example 3:
Input  :  arr[] = {10, 2, 4, 30, 35}
Output:  -1
 
Example 4:
Input :  arr[] = {10, 2, 2, 4, 30, 35}
Output:  4
Example 5:
Input  : arr[] = {17, 2, 1, 35, 30}
Output : 35
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findGreatest() which takes the array arr[] and its size N as inputs and returns the answer. If the answer is not present in the array, return -1.
Expected Time Complexity: O(N. Log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ A_{i} ≤ 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
        def findGreatest(self, arr, n):
        # Your code goes here   

Solutions:
from math import *

class Solution:

	def findGreatest(self, arr, n):
		m = dict()
		for i in arr:
			m[i] = m.get(i, 0) + 1
		arr = sorted(arr)
		for i in range(n - 1, 0, -1):
			j = 0
			if arr[i] == 1:
				if m[1] > 2:
					return 1
				continue
			while j < i and arr[j] <= sqrt(arr[i]):
				if arr[j] == 1:
					if m[arr[i]] > 1:
						return arr[i]
					j += 1
					continue
				if arr[i] % arr[j] == 0:
					result = arr[i] // arr[j]
					if result != arr[j] and result in m.keys() and (m[result] > 0):
						return arr[i]
					elif result == arr[j] and result in m.keys() and (m[result] > 1):
						return arr[i]
				j += 1
		return -1


class Solution:

	def findGreatest(self, A, n):
		hash = dict()
		for i in A:
			hash[i] = hash.get(i, 0) + 1
		A.sort()
		for i in range(n - 1, 0, -1):
			j = 0
			while j < i and A[j] <= A[i] ** 0.5:
				if A[i] % A[j] == 0:
					res = A[i] // A[j]
					if res == A[i] and hash[res] > 1 or (res != A[j] and res != A[i] and (res in hash)) or (res == A[j] and A[i] and (hash[res] > 1)):
						return A[i]
				j += 1
		return -1


class Solution:

	def findGreatest(self, arr, n):
		arr.sort(reverse=True)
		for i in range(n):
			temp = arr[i]
			low = i + 1
			high = n - 1
			while low < high:
				prod = arr[low] * arr[high]
				if prod == temp:
					return prod
				elif prod > temp:
					low += 1
				else:
					high -= 1
		return -1


import math
from collections import Counter

class Solution:

	def findGreatest(self, arr, n):
		m = Counter(arr)
		arr.sort()
		i = n - 1
		while i > 0:
			j = 0
			while j < i and arr[j] <= math.floor(math.sqrt(arr[i])):
				if arr[i] % arr[j] == 0:
					result = arr[i] // arr[j]
					if result != arr[j] and result != arr[i] and (m[result] > 0) or (result == arr[j] and m[result] > 1) or (result == arr[i] and m[result] > 1):
						return arr[i]
				j += 1
			i -= 1
		return -1


from math import sqrt

class Solution:

	def findGreatest(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		arr.sort()
		if len(d) == 1 and arr[0] == 1:
			return 1
		for i in sorted(d.keys(), reverse=True):
			for j in sorted(d.keys()):
				if j < i and i % j == 0:
					r = i // j
					if r == i:
						if d.get(i, 0) > 1:
							return i
					elif r == j:
						if d.get(j, 0) > 1:
							return j
					elif d.get(r, 0) > 0:
						return i
		return -1


from math import sqrt

class Solution:

	def findGreatest(self, arr, n):
		count = {}
		for i in arr:
			count[i] = count.get(i, 0) + 1
		arr.sort()
		for i in range(n - 1, 0, -1):
			j = 0
			while j < i and arr[j] <= sqrt(arr[i]):
				if arr[i] % arr[j] == 0:
					sec = arr[i] // arr[j]
					if sec == arr[i]:
						if sec in count.keys() and count[sec] > 1:
							return arr[i]
					elif sec == arr[j]:
						if sec in count.keys() and count[sec] > 1:
							return arr[i]
					elif sec in count.keys() and count[sec] > 0:
						return arr[i]
				j += 1
		return -1


from math import sqrt

class Solution:

	def findGreatest(self, arr, n):
		arr.sort()
		d = dict()
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in range(n - 1, 0, -1):
			j = 0
			while j < i and arr[j] <= arr[i]:
				if arr[i] % arr[j] == 0:
					res = arr[i] // arr[j]
					if (res != arr[j] and res != arr[i]) and res in d.keys() and (d[res] > 0):
						return arr[i]
					elif (res == arr[j] or res == arr[i]) and res in d.keys() and (d[res] > 1):
						return arr[i]
				j += 1
		return -1


class Solution:

	def BST(self, a, k):
		r = len(a) - 1
		l = 0
		while l <= r:
			mid = (l + r) // 2
			if a[mid] == k:
				return 1
			elif a[mid] > k:
				r = mid - 1
			else:
				l = mid + 1
		return -1

	def findGreatest(self, arr, n):
		arr.sort()
		for i in range(-1, -(n - 1), -1):
			for j in range(0, n + i):
				if arr[i] % arr[j] == 0:
					if self.BST(arr[j + 1:n + i], arr[i] // arr[j]) == 1:
						return arr[i]
		return -1


import math

class Solution:

	def findGreatest(self, arr, n):
		arr = sorted(arr)
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for i in range(n - 1, -1, -1):
			ele = arr[i]
			if dic[ele] > 1 and 1 in dic and (dic[1] > 0):
				return ele
			for j in range(i - 1):
				if ele % arr[j] == 0:
					ele_2 = ele / arr[j]
					if ele_2 in dic and arr[j] != ele_2 and (ele_2 != ele):
						return ele
		return -1


class Solution:

	def findGreatest(self, arr, n):
		hashset = {}
		sortarr = sorted(arr, reverse=True)
		for (i, num) in enumerate(sortarr):
			hashset[num] = i
		for (i, el1) in enumerate(sortarr):
			for (k, el2) in enumerate(sortarr):
				num = el1 / el2
				if num in hashset and i != k and (hashset.get(num) != i) and (hashset.get(num) != k):
					return el1
		return -1