Geek Land has a population of N people and each person's ability to rule the town is measured by a numeric value arr[i]. The two people that can together rule Geek Land must be compatible with each other i.e., the sum of digits of their ability arr[i] must be equal. Their combined ability should be maximum amongst all the possible pairs of people. Find the combined ability of the Ruling Pair.
Example 1:
Input:
N = 5
arr[] = {55, 23, 32, 46, 88}
Output:
101
Explanation:
All possible pairs that are 
compatible with each other are- (23, 32) 
with digit sum 5 and (55, 46) with digit 
sum 10. Out of these the maximum combined 
ability pair is (55, 46) i.e. 55 + 46 = 101
Example 2:
Input:
N = 4
arr[] = {18, 19, 23, 15}
Output:
-1
Explanation:
No two people are compatible with each other. 
Your Task:  
You don't need to read input or print anything. Complete the function RulingPairÃ¢â¬â¹() which takes the array arr[] and size of array N as input parameters and returns the answer. If No two people are compatible with
each other then return -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5} 
1 ≤ arr[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

#Back-end complete function Template for Python 3


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


Solutions:
class Solution:

	def sumOfDigits(self, n):
		ans = 0
		while n:
			ans += n % 10
			n //= 10
		return ans

	def RulingPair(self, arr, n):
		d = {}
		ans = -1
		for a in arr:
			k = self.sumOfDigits(a)
			if k in d:
				ans = max(ans, a + d[k])
				d[k] = max(d[k], a)
			else:
				d[k] = a
		return ans


def larg(arr):
	f = s = -100000000.0
	for i in arr:
		if i >= f:
			s = f
			f = i
		elif i >= s:
			s = i
	return f + s

class Solution:

	def RulingPair(self, arr, n):
		dic = {}
		for i in arr:
			s = 0
			temp = i
			while i:
				s += i % 10
				i //= 10
			if s not in dic:
				dic[s] = []
			dic[s].append(temp)
		m = -1
		for i in dic:
			if len(dic[i]) >= 2:
				m = max(m, larg(dic[i]))
		return m


def sum_dig(num):
	num = str(num)
	count = 0
	for i in range(len(num)):
		count += int(num[i])
	return count

def findLargestSumPair(arr, n):
	val1 = max(arr)
	ind = arr.index(val1)
	arr = arr[:ind] + arr[ind + 1:]
	val2 = max(arr)
	return val1 + val2

class Solution:

	def RulingPair(self, arr, n):
		dict = {}
		for i in range(len(arr)):
			val = sum_dig(arr[i])
			if val not in dict:
				dict[val] = [arr[i]]
			else:
				dict[val].append(arr[i])
		max_ = -1
		for val in dict:
			lng = len(dict[val])
			if lng > 1:
				max_ = max(max_, findLargestSumPair(dict[val], lng))
		return max_


def sum_dig(num):
	num = str(num)
	count = 0
	for i in range(len(num)):
		count += int(num[i])
	return count

def findLargestSumPair(arr, n):
	if arr[0] > arr[1]:
		first = arr[0]
		second = arr[1]
	else:
		first = arr[1]
		second = arr[0]
	for i in range(2, n):
		if arr[i] >= first:
			second = first
			first = arr[i]
		elif arr[i] > second and arr[i] != first:
			second = arr[i]
	return first + second

class Solution:

	def RulingPair(self, arr, n):
		dict = {}
		for i in range(len(arr)):
			val = sum_dig(arr[i])
			if val not in dict:
				dict[val] = [arr[i]]
			else:
				dict[val].append(arr[i])
		max_ = -1
		for val in dict:
			lng = len(dict[val])
			if lng > 1:
				max_ = max(max_, findLargestSumPair(dict[val], lng))
		return max_


class Solution:

	def RulingPair(self, a, n):
		d = {}
		ans = -1
		for i in range(n):
			num = a[i]
			s = 0
			while num != 0:
				s += num % 10
				num = num // 10
			if s not in d.keys():
				d[s] = a[i]
			else:
				ans = max(ans, d[s] + a[i])
				d[s] = max(d[s], a[i])
		return ans


class Solution:

	def dsum(self, n):
		summ = 0
		while n:
			r = n % 10
			summ += r
			n //= 10
		return summ

	def RulingPair(self, arr, n):
		d = {}
		for i in arr:
			k = self.dsum(i)
			if k in d:
				d[k] += [i]
			else:
				d[k] = [i]
		res = -1
		for v in d.values():
			ans = 0
			if len(v) > 1:
				v.sort()
				ans = v[-1] + v[-2]
				if res < ans:
					res = ans
		return res


class Solution:

	def RulingPair(self, arr, n):
		sums = {}
		maxi = -1
		for item in arr:
			summa = sum(map(int, str(item)))
			if summa not in sums:
				sums[summa] = item
			else:
				maxi = max(maxi, sums[summa] + item)
				sums[summa] = max(sums[summa], item)
		return maxi


class Solution:

	def RulingPair(self, arr, n):

		def helper(n):
			res = 0
			while n:
				res += n % 10
				n = n // 10
			return res
		d = {}
		for (i, ele) in enumerate(arr):
			x = helper(ele)
			if x not in d:
				d[x] = [ele]
			else:
				d[x].append(ele)
		maxi = -1
		for (k, v) in d.items():
			tmp_list = sorted(v)
			if len(tmp_list) >= 2:
				maxi = max(tmp_list[-1] + tmp_list[-2], maxi)
		return maxi


from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):
		ha = defaultdict(int)
		maxi = -1
		for i in range(n):
			l = sum(list(map(int, str(arr[i]))))
			su = 0
			maxil = 0
			if l in ha:
				su = arr[i]
				su += ha[l]
				maxi = max(su, maxi)
				maxil = max(arr[i], ha[l])
				ha[l] = maxil
			else:
				ha[l] = arr[i]
		return maxi


class Solution:

	def RulingPair(self, arr, n):

		def h(x):
			x = str(x)
			ans = 0
			for i in x:
				ans += int(i)
			return ans
		d = {}
		for i in arr:
			a = h(i)
			if a not in d:
				d[a] = [i]
			else:
				d[a].append(i)
		ans = []
		for i in d:
			a = d[i]
			if len(a) > 1:
				a.sort()
				ans.append(a[-1] + a[-2])
		if ans:
			return max(ans)
		return -1


from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):
		d = defaultdict(list)
		for i in arr:
			sum = 0
			for j in str(i):
				sum += int(j)
			d[sum].append(i)
		flag = 0
		max1 = -1000000
		for i in d:
			if len(d[i]) > 1:
				flag = 1
				d[i].sort(reverse=True)
				max1 = max(max1, d[i][0] + d[i][1])
		if flag == 0:
			return -1
		return max1


from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):
		d = defaultdict(list)
		mx = 0
		for num in arr:
			n = num
			Sum = 0
			while n:
				Sum = Sum + n % 10
				n = n // 10
			d[Sum].append(num)
		lst = [sum(sorted(v, reverse=True)[:2]) for (k, v) in d.items() if len(v) > 1]
		if len(lst) > 0:
			return max(lst)
		else:
			return -1


class Solution:

	def dig_sum(self, n):
		c = 0
		while n != 0:
			c += n % 10
			n = n // 10
		return c

	def RulingPair(self, arr, n):
		s = {}
		for i in arr:
			m = self.dig_sum(i)
			if m in s:
				s[m].append(i)
			else:
				s[m] = [i]
		d = -1
		for i in s:
			if len(s[i]) >= 2:
				s[i].sort()
				e = s[i][-1] + s[i][-2]
				if e > d:
					d = e
		return d


class Solution:

	def RulingPair(self, arr, n):
		d = {}
		for i in range(n):
			k = sum(list([int(s) for s in str(arr[i])]))
			if k in d:
				d[k].append(arr[i])
			else:
				d[k] = [arr[i]]
		m1 = -1
		for k in d.keys():
			if len(d[k]) > 1:
				t = d[k]
				t.sort()
				t.reverse()
				m1 = max(m1, t[0] + t[1])
		return m1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.RulingPair(arr, n))


from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):
		mx = 0
		d = defaultdict(int)
		for i in arr:
			sm = 0
			s = str(i)
			for j in s:
				sm += int(j)
			if sm not in d:
				d[sm] = i
			else:
				mx = max(d[sm] + i, mx)
				if i > d[sm]:
					d[sm] = i
		if mx == 0:
			return -1
		return mx
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.RulingPair(arr, n))


from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):
		d = defaultdict(list)
		mx = 0
		for num in arr:
			n = num
			Sum = 0
			while n:
				Sum = Sum + n % 10
				n = n // 10
			d[Sum].append(num)
		lst = [sum(sorted(v, reverse=True)[:2]) for (k, v) in d.items() if len(v) > 1]
		if len(lst) > 0:
			return max(lst)
		else:
			return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.RulingPair(arr, n))


class Solution:

	def RulingPair(self, a, n):
		d = dict()
		ans = -1

		def digitSum(num):
			summ = 0
			while num != 0:
				rem = num % 10
				summ += rem
				num = num // 10
			return summ
		s = 0
		for i in range(n):
			s = digitSum(a[i])
			if s not in d:
				d[s] = a[i]
			else:
				ans = max(ans, d[s] + a[i])
				d[s] = max(d[s], a[i])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		print(obj.RulingPair(arr, n))


class Solution:

	def RulingPair(self, arr, n):
		m = {}
		m1 = {}
		for i in range(n):
			z = arr[i]
			su = 0
			while z > 0:
				su = su + z % 10
				z = z // 10
			m1[i] = su
			if su in m:
				if arr[i] > arr[m[su]]:
					m[su] = i
			else:
				m[su] = i
		ma = -1
		for i in range(n):
			s = m1[i]
			mfs = m[s]
			if i != mfs:
				ma = max(ma, arr[i] + arr[m[s]])
		return ma


class Solution:

	def RulingPair(self, arr, n):
		m = {}
		for i in arr:
			s = 0
			l = str(i)
			for j in l:
				s = s + int(j)
			if m.get(s, []) == []:
				m[s] = [i]
			else:
				p = m.get(s)
				p.append(i)
				m[s] = p
		max_sum = -1
		for i in m.keys():
			v = m.get(i)
			if len(v) > 1:
				v.sort(reverse=True)
				s = v[0] + v[1]
				if s > max_sum:
					max_sum = s
		return max_sum


class Solution:

	def RulingPair(self, arr, n):
		digsumdict = {}
		for num in arr:
			digsum = 0
			for y in str(num):
				digsum += int(y)
			if digsum in digsumdict.keys():
				digsumdict[digsum].append(num)
			else:
				digsumdict[digsum] = [num]
		maxval = -1
		sumval = -1
		for (k, v) in digsumdict.items():
			if len(v) > 1:
				vals = sorted(v, reverse=True)
				sumval = vals[0] + vals[1]
			if sumval > maxval:
				maxval = sumval
		return maxval


from collections import defaultdict

def digitsum(n):
	r = 0
	while n:
		(r, n) = (r + n % 10, n // 10)
	return r

class Solution:

	def RulingPair(self, arr, n):
		dd = defaultdict(list)
		for x in arr:
			dd[digitsum(x)].append(x)
		matches = [sum(sorted(v, reverse=True)[:2]) for (k, v) in dd.items() if len(v) > 1]
		if len(matches) > 0:
			return max(matches)
		else:
			return -1


class Solution:

	def digitSum(self, n):
		s = 0
		while n != 0:
			s += n % 10
			n = n // 10
		return s

	def RulingPair(self, arr, n):
		max_rulers = {}
		best = -1
		for el in arr:
			ds = self.digitSum(el)
			if ds in max_rulers:
				if len(max_rulers[ds]) == 1:
					max_rulers[ds].append(el)
					best = max(best, sum(max_rulers[ds]))
				else:
					m = min(max_rulers[ds])
					if m < el:
						max_rulers[ds][max_rulers[ds].index(m)] = el
						best = max(best, sum(max_rulers[ds]))
			else:
				max_rulers[ds] = [el]
		return best


from collections import Counter

class Solution:

	def RulingPair(self, arr, n):
		c = Counter(arr)
		A = []
		di = {}
		maxi = -1
		d = arr.copy()
		s = set()
		for i in range(n):
			sum = 0
			while d[i] > 0:
				sum = sum + d[i] % 10
				d[i] = d[i] // 10
			if sum in s and arr[i] + di[sum] > maxi:
				maxi = arr[i] + di[sum]
			else:
				s.add(sum)
			if sum in di:
				if di[sum] < arr[i]:
					di[sum] = arr[i]
			else:
				di[sum] = arr[i]
		return maxi


class Solution:

	def RulingPair(self, arr, n):
		pairs = []
		hmap = {}
		for i in range(0, n):
			t = arr[i]
			sum_digit = 0
			while t > 0:
				sum_digit += t % 10
				t = t // 10
			if sum_digit in hmap:
				pairs.append(arr[hmap[sum_digit]] + arr[i])
				if arr[hmap[sum_digit]] < arr[i]:
					hmap[sum_digit] = i
			else:
				hmap[sum_digit] = i
		return max(pairs) if len(pairs) > 0 else -1


class Solution:

	def digitSum(self, n):
		sum = 0
		while n:
			sum += n % 10
			n //= 10
		return sum

	def RulingPair(self, arr, n):
		map = dict()
		ans = -1
		for i in range(n):
			dSum = self.digitSum(arr[i])
			if dSum in map:
				ans = max(ans, map[dSum] + arr[i])
			map[dSum] = max(map.get(dSum, 0), arr[i])
		return ans


from itertools import combinations

class Solution:

	def RulingPair(self, arr, n):
		ans = -1
		hmap = {}
		arr.sort()
		for i in arr:
			sum1 = sum(list(map(int, str(i))))
			if sum1 in hmap:
				hmap[sum1].append(i)
			else:
				hmap[sum1] = [i]
		for i in hmap:
			if len(hmap[i]) >= 2:
				ans = max(ans, hmap[i][-1] + hmap[i][-2])
		return ans


class Solution:

	def digitSum(self, n):
		ans = 0
		for i in str(n):
			ans += int(i)
		return ans

	def RulingPair(self, arr, n):
		ans = -1
		dic = {}
		for i in arr:
			sm = self.digitSum(i)
			if sm in dic:
				ans = max(ans, i + dic[sm])
				dic[sm] = max(dic[sm], i)
			else:
				dic[sm] = i
		return ans


class Solution:

	def RulingPair(self, arr, n):
		d = {}
		h = -1
		arr.sort()
		for i in arr:
			s = sum(list(map(int, str(i))))
			if s in d:
				d[s].append(i)
			else:
				d[s] = [i]
		for i in d:
			if len(d[i]) >= 2:
				h = max(h, d[i][-1] + d[i][-2])
		return h


class Solution:

	def RulingPair(self, arr, n):
		str_val = {}
		maxv = -1
		for i in arr:
			s = str(i)
			x = 0
			for j in s:
				x += int(j)
			if x in str_val.keys():
				maxv = max(maxv, int(s) + str_val[x])
				str_val[x] = max(str_val[x], i)
			else:
				str_val[x] = i
		return maxv


class Solution:

	def RulingPair(self, arr, n):
		mydict = {}
		for i in arr:
			s = str(i)
			summ = 0
			for j in s:
				summ += int(j)
			if summ in mydict:
				mydict[summ].append(i)
			else:
				mydict[summ] = [i]
		maxx = -1
		for i in mydict:
			if len(mydict[i]) >= 2:
				lst = mydict[i]
				lst.sort()
				summ = lst[-1] + lst[-2]
				if summ > maxx:
					maxx = summ
		return maxx


def digitSum(n):
	sum = 0
	for digit in str(n):
		sum += int(digit)
	return sum

class Solution:

	def RulingPair(self, arr, n):
		d = {}
		ans = -1
		for i in arr:
			digit_sum = digitSum(i)
			if digit_sum not in d:
				d[digit_sum] = i
			else:
				ans = max(ans, i + d[digit_sum])
				d[digit_sum] = max(i, d[digit_sum])
		if ans == -1:
			return -1
		else:
			return ans


class Solution:

	def RulingPair(self, arr, n):
		maxsum = -1
		digitmap = {}
		for i in arr:
			digitsum = 0
			tmp = i
			while tmp > 0:
				digitsum += tmp % 10
				tmp //= 10
			maxval = digitmap.get(digitsum)
			if not maxval:
				digitmap[digitsum] = i
			else:
				sumof = i + maxval
				maxsum = max(maxsum, sumof)
				if i > maxval:
					digitmap[digitsum] = i
		return maxsum


class Solution:

	def RulingPair(self, arr, n):
		ma = 0
		d = {}
		for i in arr:
			s = 0
			x = i
			while x:
				s += x % 10
				x = x // 10
			t = s
			if d.get(t) == None:
				d[t] = i
			else:
				ma = max(ma, i + d[t])
				d[t] = max(d[t], i)
		if ma == 0:
			return -1
		else:
			return ma


class Solution:

	def sumDigit(self, n1):
		sum1 = 0
		while n1 > 0:
			sum1 += n1 % 10
			n1 = n1 // 10
		return sum1

	def RulingPair(self, arr, n):
		dic = {}
		temp = -1
		for i in range(n):
			n2 = self.sumDigit(arr[i])
			if n2 not in dic:
				dic[n2] = i
			else:
				if temp < arr[dic[n2]] + arr[i]:
					temp = arr[dic[n2]] + arr[i]
				if arr[i] > arr[dic[n2]]:
					dic[n2] = i
		return temp


class Solution:

	def digsum(self, num):
		ans = 0
		while num:
			ans += num % 10
			num //= 10
		return ans

	def util(self, arr):
		if arr[0] > arr[1]:
			maxx = arr[0]
			smaxx = arr[1]
		else:
			maxx = arr[1]
			smaxx = arr[0]
		n = len(arr)
		for i in range(2, n):
			if arr[i] > maxx:
				smaxx = maxx
				maxx = arr[i]
			elif arr[i] > smaxx:
				smaxx = arr[i]
		return (maxx, smaxx)

	def RulingPair(self, arr, n):
		dic = {}
		ans = float('-inf')
		for i in arr:
			z = self.digsum(i)
			if z in dic:
				dic[z].append(i)
			else:
				dic[z] = [i]
		for key in dic:
			if len(dic[key]) > 1:
				(maxx, smaxx) = self.util(dic[key])
				ans = max(ans, maxx + smaxx)
		if ans != float('-inf'):
			return ans
		return -1


class Solution:

	def RulingPair(self, arr, n):
		keys = []
		vals = dict()
		ans = -1
		for i in arr:
			x = sum([int(j) for j in str(i)])
			if x in keys:
				if len(vals[x]) == 1:
					y = vals[x]
					y.append(i)
					if sum(y) > ans:
						ans = sum(y)
					vals[x] = y
				elif len(vals[x]) == 2:
					z = vals[x]
					z.append(i)
					z.remove(min(z))
					if sum(z) > ans:
						ans = sum(z)
					vals[x] = z
			else:
				keys.append(x)
				vals[x] = [i]
		return ans


class Solution:

	def RulingPair(self, arr, n):

		def digitSum(x):
			s1 = 0
			while x > 0:
				s1 += x % 10
				x = x // 10
			return s1
		ans = -1
		dic = {}
		for i in range(len(arr)):
			s = digitSum(arr[i])
			if s not in dic:
				dic[s] = arr[i]
			else:
				ans = max(ans, arr[i] + dic[s])
				dic[s] = max(dic[s], arr[i])
		return ans


from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):
		dict_1 = defaultdict(list)
		for i in arr:
			temp = 0
			j = i
			while j:
				temp += j % 10
				j //= 10
			dict_1[temp].append(i)
		ans = 0
		for i in dict_1.keys():
			if len(dict_1[i]) >= 2:
				dict_1[i].sort(reverse=True)
				ans = max(ans, dict_1[i][0] + dict_1[i][1])
		return ans if ans != 0 else -1


class Solution:

	def RulingPair(self, arr, n):
		l = [str(i) for i in arr]
		l1 = []
		for v in l:
			x = [int(i) for i in list(v)]
			s = sum(x)
			l1.append(s)
		d = {}
		for i in range(len(l1)):
			if l1[i] in d:
				d[l1[i]].append(arr[i])
			else:
				d[l1[i]] = [arr[i]]
		mx = 0
		mx1 = 0
		if len(d) == len(l1):
			return -1
		for k in d:
			if len(d[k]) <= 1:
				continue
			elif k > mx1:
				v = d[k]
				v.sort(reverse=True)
				s = sum(v[:2])
				mx = max(mx, s)
		return mx


class Solution:

	def RulingPair(self, arr, n):
		d = {}
		for i in arr:
			x = sum(list(map(int, str(i))))
			if d.get(x):
				d[x].append(i)
			else:
				d[x] = [i]
		ans = -1
		for i in d:
			if len(d[i]) > 1:
				if len(d[i]) > 2:
					if sum(sorted(d[i], reverse=True)[:2]) > ans:
						ans = sum(sorted(d[i], reverse=True)[:2])
				elif sum(d[i]) > ans:
					ans = sum(d[i])
		return ans


class Solution:

	def summ(self, n):
		sum = 0
		while n > 0:
			sum += n % 10
			n = n // 10
		return sum

	def RulingPair(self, arr, N):
		maxi = -1
		d = {}
		for i in range(N):
			s = self.summ(arr[i])
			if s not in d:
				d[s] = [arr[i]]
			else:
				d[s].append(arr[i])
		for key in d:
			if len(d[key]) >= 2:
				a1 = max(d[key])
				d[key].remove(a1)
				a2 = max(d[key])
				sum = a1 + a2
				if sum > maxi:
					maxi = sum
		return maxi


class Solution:

	def RulingPair(self, arr, n):
		arr.sort(reverse=True)
		hm = {}
		for i in arr:
			n = i
			a = 0
			while n:
				a += n % 10
				n = n // 10
			if a in hm:
				if hm[a][1] == 0:
					hm[a][0] += i
					hm[a][1] = 1
			else:
				hm[a] = [i, 0]
		ans = -1
		for i in hm:
			if hm[i][1]:
				ans = max(ans, hm[i][0])
		return ans


class Solution:

	def RulingPair(self, arr, n):
		comp = {}
		for i in range(n):
			dabs = self.getDigitsSum(arr[i])
			if dabs in comp:
				comp[dabs].append(arr[i])
			else:
				comp[dabs] = [arr[i]]
		res = -1
		for k in comp.keys():
			res = max(res, self.getAbility(comp[k]))
		return res

	def getDigitsSum(self, x):
		res = 0
		while x > 0:
			res += x % 10
			x = x // 10
		return res

	def getAbility(self, A):
		if len(A) < 2:
			return -1
		mx = 0
		mx_pr = 0
		for e in A:
			if e >= mx:
				mx_pr = mx
				mx = e
		for e in A:
			if e != mx:
				mx_pr = max(mx_pr, e)
		return mx + mx_pr


class Solution:

	def RulingPair(self, arr, n):
		d = {}
		m = -1
		for i in arr:
			s = 0
			j = i
			while j:
				s += j % 10
				j //= 10
			if s in d.keys():
				m = max(m, d[s] + i)
				if d[s] < i:
					d[s] = i
			else:
				d[s] = i
		return m


class Solution:

	def RulingPair(self, arr, n):
		map_ = {}
		res = -1
		for i in range(len(arr)):
			sum_ = sum([int(a) for a in str(arr[i])])
			if map_.get(sum_):
				res = max(res, map_.get(sum_) + arr[i])
				map_[sum_] = max(map_[sum_], arr[i])
			else:
				map_[sum_] = arr[i]
		return res


class Solution:

	def RulingPair(self, arr, n):
		res = -1
		d = {}
		for i in arr:
			digisum = sum((int(x) for x in str(i)))
			if digisum in d:
				res = max(res, i + d[digisum])
				i = max(i, d[digisum])
			d[digisum] = i
		return res


class Solution:

	def dsum(self, n):
		s = 0
		while n > 0:
			s = s + n % 10
			n = n // 10
		return s

	def RulingPair(self, arr, n):
		res = -1
		mp = dict()
		for i in range(n):
			nsm = self.dsum(arr[i])
			if nsm in mp:
				res = max(res, mp[nsm] + arr[i])
			mp[nsm] = max(mp.get(nsm, 0), arr[i])
		return res


class Solution:

	def RulingPair(self, arr, n):

		def func(item):
			su = 0
			while item > 0:
				rem = item % 10
				su += rem
				item = item // 10
			return su
		from collections import defaultdict
		dic = defaultdict(list)
		for item in arr:
			ans = func(item)
			if len(dic[ans]) < 2:
				dic[ans].append(item)
			elif item > dic[ans][0] and item > dic[ans][1]:
				second = max(dic[ans][0], dic[ans][1])
				dic[ans][0] = item
				dic[ans][1] = second
			elif item > dic[ans][0]:
				dic[ans][0] = item
			elif item > dic[ans][1]:
				dic[ans][1] = item
		ma = -1
		for (k, v) in dic.items():
			if len(v) == 2:
				one = v[0]
				two = v[1]
				ma = max(ma, one + two)
		return ma


class Solution:

	def sod(self, num):
		sum = 0
		while num != 0:
			sum = sum + int(num % 10)
			num = int(num / 10)
		return sum

	def RulingPair(self, arr, n):
		hash = {}
		for i in range(100):
			hash[i] = 0
		ans = -1
		for i in range(n):
			s = self.sod(arr[i])
			if s in hash and hash[s] != 0:
				ans = max(ans, hash[s] + arr[i])
			hash[s] = max(hash[s], arr[i])
		return ans


class Solution:

	def RulingPair(self, arr, n):
		dt = {}
		arr.sort()
		for i in arr:
			sm = sum(list(map(int, list(str(i)))))
			try:
				dt[sm].append(i)
			except KeyError:
				dt[sm] = [i]
		ans = -1
		for (key, value) in dt.items():
			if len(value) > 1:
				ans = max(ans, value[-1] + value[-2])
		return ans


from itertools import combinations

class Solution:

	def digitSum(self, n):
		sum = 0
		while n:
			sum += n % 10
			n //= 10
		return sum

	def RulingPair(self, arr, n):
		mp = dict()
		ans = -1
		for i in range(n):
			dSum = self.digitSum(arr[i])
			if dSum in mp:
				ans = max(ans, mp[dSum] + arr[i])
			mp[dSum] = max(mp.get(dSum, 0), arr[i])
		return ans


def func(n: int) -> int:
	return sum(map(int, str(n)))

class Solution:

	def RulingPair(self, arr, n):
		l1 = sorted([(func(arr[i]), arr[i]) for i in range(n)], reverse=True)
		ans = -1
		for i in range(n - 1):
			if l1[i][0] == l1[i + 1][0]:
				ans = max(ans, l1[i][1] + l1[i + 1][1])
		return ans


class Solution:

	def RulingPair(self, arr, n):
		sum_map = {}
		for i in arr:
			num = str(i)
			s = 0
			for j in num:
				s += int(j)
			if s in sum_map:
				sum_map[s].append(i)
			elif s not in sum_map:
				sum_map[s] = [i]
		high = 0
		for i in sum_map:
			l = sum_map[i]
			if 3 > len(l) > 1:
				s = sum(l)
				if s > high:
					high = s
			elif len(l) > 2:
				l.sort(reverse=True)
				s = sum(l[:2])
				if s > high:
					high = s
		return high if high > 0 else -1


class Solution:

	def RulingPair(self, arr, n):
		d = dict()
		for i in arr:
			s = 0
			for j in str(i):
				s = s + int(j)
			if d.get(s) != None:
				d[s].append(i)
			if d.get(s) == None:
				d[s] = [i]
		for i in d.keys():
			d[i].sort()
		s = 0
		for i in d.keys():
			if len(d[i]) > 1:
				s = max(s, d[i][len(d[i]) - 1] + d[i][len(d[i]) - 2])
		if s == 0:
			return -1
		return s


from collections import defaultdict
import heapq

class Solution:

	def digit(self, num):
		sum = 0
		while num > 0:
			sum += num % 10
			num = num // 10
		return sum

	def RulingPair(self, arr, n):
		m = float('-inf')
		hash_data = defaultdict(list)
		for each in arr:
			num = self.digit(each)
			heapq.heappush(hash_data[num], -each)
		for val_list in hash_data.values():
			if len(val_list) >= 2:
				temp = 0
				temp += -heapq.heappop(val_list)
				temp += -heapq.heappop(val_list)
				m = max(m, temp)
		if m == float('-inf'):
			return -1
		return m


class Solution:

	def RulingPair(self, arr, n):
		groups = {}
		for v in arr:
			s = 0
			for d in str(v):
				s += int(d)
			try:
				groups[s].append(v)
			except:
				groups[s] = [v]
		max_ = -1
		for key in groups.keys():
			pairs = groups[key]
			if len(pairs) < 2:
				continue
			pairs.sort(reverse=True)
			if pairs[0] + pairs[1] > max_:
				max_ = pairs[0] + pairs[1]
		return max_


import math

class Solution:

	def RulingPair(self, arr, n):
		a = []
		d = {}
		sum_of_digits = 0
		for i in range(len(arr)):
			sum_of_digits = sum((int(digit) for digit in str(arr[i])))
			if sum_of_digits in d:
				if d[sum_of_digits][0] < arr[i] and d[sum_of_digits][1] <= arr[i]:
					d[sum_of_digits][0] = d[sum_of_digits][1]
					d[sum_of_digits][1] = arr[i]
				elif d[sum_of_digits][0] > arr[i] and d[sum_of_digits][1] > arr[i]:
					pass
				elif d[sum_of_digits][0] < arr[i] and d[sum_of_digits][1] > arr[i]:
					d[sum_of_digits][0] = arr[i]
			else:
				d[sum_of_digits] = [-math.inf, arr[i]]
		for i in d:
			d[i] = sum(d[i])
		ans = max(d.values())
		if ans < 1:
			return -1
		return ans


import math

class Solution:

	def RulingPair(self, arr, n):
		d = {}
		sum_of_digits = 0
		ans = -1
		for i in range(len(arr)):
			sum_of_digits = sum((int(digit) for digit in str(arr[i])))
			if sum_of_digits in d:
				ans = max(ans, d[sum_of_digits] + arr[i])
				d[sum_of_digits] = max(d[sum_of_digits], arr[i])
			else:
				d[sum_of_digits] = arr[i]
		return ans


class Solution:

	def RulingPair(self, arr, n):
		x = []

		def sumi(x):
			s = 0
			while x > 0:
				s = s + x % 10
				x = x // 10
			return s
		d = {}
		for i in arr:
			a = sumi(i)
			if a not in d:
				d[a] = [i]
			else:
				d[a].append(i)
		for i in d:
			if len(d[i]) > 1:
				d[i].sort(reverse=True)
		for i in d:
			if len(d[i]) > 1:
				y = d[i][0] + d[i][1]
				x.append(y)
		if len(x) == 0:
			return -1
		return max(x)


class Solution:

	def findsum(self, a):
		s = 0
		while a != 0:
			s += int(a % 10)
			a = int(a / 10)
		return s

	def RulingPair(self, arr, n):
		d = {}
		m = -1
		for x in arr:
			s = self.findsum(x)
			if s not in d:
				d[s] = x
			else:
				m = max(m, x + d[s])
				d[s] = max(x, d[s])
		return m


class Solution:

	def RulingPair(self, arr, n):
		best_pair = -1
		sums = {}
		for v in arr:
			sum = Solution.dig_sum(v)
			prev_val = sums.get(sum)
			if prev_val is not None:
				if v + prev_val > best_pair:
					best_pair = v + prev_val
				if prev_val >= v:
					continue
			sums[sum] = v
		return best_pair

	@staticmethod
	def dig_sum(n: int) -> int:
		res = 0
		while n > 0:
			res += n % 10
			n //= 10
		return res


from functools import reduce
from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):
		out = -1
		d = defaultdict(list)
		for i in arr:
			s = int(reduce(lambda a, b: int(a) + int(b), str(i)))
			if len(d[s]) == 0 or len(d[s]) == 1:
				d[s].append(i)
			elif len(d[s]) == 2:
				minimum_value = min(d[s])
				if minimum_value < i:
					d[s].remove(minimum_value)
					d[s].append(i)
			if len(d[s]) > 1:
				total = sum(d[s])
				if total > out:
					out = total
		return out


class Solution:

	def RulingPair(self, arr, n):
		d = dict()
		ms = -1
		for num in arr:
			s = 0
			a = num
			while num:
				s = s + num % 10
				num = num // 10
			v = s
			if v not in d:
				d[v] = a
			else:
				ts = a + d[v]
				if ts > ms:
					ms = ts
				if d[v] < a:
					d[v] = a
		return ms


class Solution:

	def RulingPair(self, l, n):

		def fun(n):
			ans = 0
			while n > 0:
				ans += n % 10
				n //= 10
			return ans
		dic = dict()
		for i in l:
			s = fun(i)
			if s in dic:
				dic[s].append(i)
				dic[s].sort()
				if len(dic[s]) == 3:
					dic[s].pop(0)
			else:
				dic[s] = [i]
		ans = -1
		for i in dic:
			if len(dic[i]) == 2:
				ans = max(ans, dic[i][0] + dic[i][1])
		return ans


class Solution:

	def RulingPair(self, arr, n):
		d = {}
		ans = -1
		for num in arr:
			val = 0
			t = num
			while num > 0:
				rem = num % 10
				num = num // 10
				val += rem
			if val not in d:
				d[val] = t
			else:
				ans = max(ans, t + d[val])
				d[val] = max(d[val], t)
		return ans


class Solution:

	def RulingPair(self, arr, n):
		d = {}
		res = -1
		m = 0
		for i in arr:
			s = 0
			for j in str(i):
				s = s + int(j)
			if s in d:
				m = d[s] + i
				res = max(m, res)
				if i > d[s]:
					d[s] = i
			else:
				d[s] = i
		return res


import heapq, collections

class Solution:

	def RulingPair(self, arr, n):
		d = collections.defaultdict(list)
		for num in arr:
			sum = 0
			for val in str(num):
				sum += int(val)
			if len(d[sum]) >= 2:
				heapq.heappushpop(d[sum], num)
			else:
				heapq.heappush(d[sum], num)
		ans = -1
		for (key, value) in d.items():
			if len(value) == 2:
				ans = max(ans, value[0] + value[1])
		return ans


class Solution:

	def sumOfDigit(self, n):
		ans = 0
		for i in str(n):
			ans += int(i)
		return ans

	def RulingPair(self, arr, n):
		d = dict()
		mx = 0
		for i in arr:
			s = self.sumOfDigit(i)
			if s in d:
				d[s].append(i)
			else:
				d[s] = [i]
		for i in d:
			ans = 0
			if len(d[i]) != 1:
				d[i].sort(reverse=True)
				mx = max(d[i][0] + d[i][1], mx)
		return mx if mx != 0 else -1


class Solution:

	def RulingPair(self, arr, n):
		temp = []
		var = ''
		ans = 0
		lst = []
		arr.sort(reverse=True)

		def check_sum(str1):
			sum1 = 0
			for i in str1:
				sum1 = sum1 + int(i)
			return sum1
		for i in range(n):
			var = var + str(arr[i])
			x = check_sum(var)
			if x in lst:
				indd = lst.index(x)
				ans = arr[indd] + arr[i]
				temp.append(ans)
			else:
				lst.append(x)
			var = ''
		if ans == 0:
			return -1
		else:
			return max(temp)


class Solution:

	def RulingPair(self, arr, n):
		dic = {}
		ans = -1
		for item in arr:
			temp = item
			sod = 0
			while temp != 0:
				sod += temp % 10
				temp = temp // 10
			if sod in dic:
				dic[sod].append(item)
			else:
				dic[sod] = [item]
		for (key, value) in dic.items():
			total = 0
			total += dic[key].pop(value.index(max(value)))
			if len(dic[key]) != 0:
				total += dic[key].pop(value.index(max(value)))
			else:
				continue
			if total > ans:
				ans = total
		return ans


class Solution:

	def RulingPair(self, a, n):
		s = sorted([(sum(map(int, str(x))), x) for x in a])
		ans = 0
		while len(s) > 1:
			if s[-1][0] == s[-2][0]:
				x = s.pop()[1] + s.pop()[1]
				ans = max(ans, x)
			else:
				s.pop()
		return -1 if ans <= 0 else ans


from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):

		def FindSum(n):
			s = list(str(n))
			s = [int(i) for i in s]
			su = sum(s)
			return su
		dicc = defaultdict(list)
		for i in arr:
			su = FindSum(i)
			dicc[su].append(i)
		if len(dicc) == len(arr):
			return -1
		mx = 0
		for i in dicc:
			if len(dicc[i]) < 2:
				continue
			dicc[i].sort()
			finSum = dicc[i][-1] + dicc[i][-2]
			mx = max(mx, finSum)
		return mx


from collections import defaultdict

class Solution:

	def digit(self, n):
		ans = 0
		while n:
			rem = n % 10
			ans += rem
			n = n // 10
		return ans

	def RulingPair(self, arr, n):
		d = defaultdict(list)
		maxi = -10 ** 9
		for i in range(n):
			digitSum = self.digit(arr[i])
			d[digitSum].append(arr[i])
		for val in d.values():
			if len(val) >= 2:
				val.sort(reverse=True)
				temp = val[0] + val[1]
				if temp > maxi:
					maxi = temp
		if maxi == -10 ** 9:
			return -1
		else:
			return maxi


from collections import defaultdict

class Solution:

	def RulingPair(self, arr, n):
		dict1 = defaultdict(list)
		for num in arr:
			sum1 = 0
			temp = num
			while num > 0:
				sum1 += num % 10
				num = num // 10
			dict1[sum1].append(temp)
		max1 = -1
		for key in dict1:
			if len(dict1[key]) > 1:
				temp_list = dict1[key]
				temp_list.sort()
				max1 = max(max1, temp_list[-1] + temp_list[-2])
		return max1


class Solution:

	def digitsum(self, num):
		sm = 0
		while num > 0:
			sm += num % 10
			num = num // 10
		return sm

	def RulingPair(self, arr, n):
		ans = -1
		hmap = [0] * 100
		for i in range(n):
			sm = self.digitsum(arr[i])
			if hmap[sm] != 0:
				ans = max(ans, hmap[sm] + arr[i])
			hmap[sm] = max(hmap[sm], arr[i])
		return ans


class Solution:

	def RulingPair(self, arr, n):

		def sod(no):
			s = 0
			while no > 0:
				s += no % 10
				no = no // 10
			return s
		d = {}
		ans = float('-inf')
		for i in range(n):
			s = sod(arr[i])
			if s in d:
				ans = max(ans, d[s] + arr[i])
				d[s] = max(d[s], arr[i])
			else:
				d[s] = arr[i]
		if ans == float('-inf'):
			return -1
		return ans


class Solution:

	def RulingPair(self, arr, n):

		def sumOfDigits(num):
			sum = 0
			a = int(num)
			while a > 0:
				sum += a % 10
				a = int(a / 10)
			return sum
		sum = 0
		flag = 0
		sumList = {}
		for nums in arr:
			sod = sumOfDigits(nums)
			if sod in sumList:
				flag = 1
				sum = max(sum, nums + sumList[sod])
				sumList[sod] = max(sumList[sod], nums)
			else:
				sumList[sod] = nums
		return sum if flag else -1


class Solution:

	def digitSum(self, n):
		return sum(map(int, list(str(n))))

	def topTwo(self, arr):
		arr = sorted(arr)
		return arr[-1] + arr[-2] if len(arr) > 1 else -1

	def RulingPair(self, arr, n):
		a = {}
		for i in arr:
			k = self.digitSum(i)
			if k not in a:
				a[k] = [i]
			else:
				a[k] += [i]
		p = -1
		for j in a.values():
			p = max(p, self.topTwo(j))
		return p


class Solution:

	def RulingPair(self, arr, n):

		def digit(i):
			s = 0
			while i > 0:
				s = s + i % 10
				i = i // 10
			return s
		d = {}
		l = -1
		for i in arr:
			a = digit(i)
			if a in d.keys():
				l = max(l, d[a] + i)
				if i > d[a]:
					d[a] = i
			else:
				d[a] = i
		return l