Given an array A of integers. Find three numbers such that sum of two elements equals the third element and return the triplet in a container result, if no such triplet is found return the container as empty.
Input:
First line of input contains number of testcases. For each testcases there will two lines. First line contains size of array and next line contains array elements.
Output:
For each test case output the triplets, if any triplet found from the array, if no such triplet is found, output -1.
Your Task: Your task is to complete the function to find triplet and return container containing result.
Constraints:
1 <= T <= 100
1 <= N <= 10^{3}
0 <= A_{i} <= 10^{5}
Example:
Input:
3
5
1 2 3 4 5
3
3 3 3
6
8 10 16 6 15 25
Output:
1
-1
1
Explanation:
Testcase 1:
Triplet Formed: {2, 1, 3}
Hence 1 
Test Case 2:
Triplet Formed: {}
Hence -1
Test Case 3:
Triplet Formed: {10, 15, 25}
Hence 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

# function should return a triplet
# if no such triplet is found return
# a container results as empty
def findTriplet(arr,n):
    # your code here



Solutions:
def findTriplet(arr, n):
	arr.sort(reverse=True)
	for i in range(n - 2):
		j = i + 1
		k = n - 1
		while j < k:
			if arr[i] == arr[j] + arr[k]:
				return [arr[i], arr[j], arr[k]]
			elif arr[i] < arr[j] + arr[k]:
				j += 1
			else:
				k -= 1
	return []


def findTriplet(arr, n):
	arr.sort()
	i = n - 2
	while i > 0:
		j = 0
		k = i - 1
		while j < k:
			if arr[i] == arr[j] + arr[k]:
				return [arr[i], arr[j], arr[k]]
			elif arr[i] > arr[j] + arr[k]:
				j += 1
			else:
				k -= 1
		i -= 1
	return []


def findTriplet(arr, n):
	arr.sort()
	for i in range(1, n):
		j = 0
		k = n - 1
		while j < k:
			if arr[j] + arr[k] == arr[i]:
				return [arr[i], arr[j], arr[k]]
			elif arr[j] + arr[k] < arr[i]:
				j += 1
			else:
				k -= 1
	return []


def findTriplet(arr, n):
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] + arr[j] in arr:
				return [arr[i], arr[j], arr[i] + arr[j]]
	return [-1]


def findTriplet(arr, n):
	arr_set = set(map(lambda i: i, arr))
	for i in range(n - 1):
		for j in range(i + 1, n):
			sum = arr[i] + arr[j]
			if sum in arr_set:
				return [0, 0, 0]
	return []


def findTriplet(arr, n):
	arr.sort()
	for i in range(n - 2):
		for j in range(i + 1, n - 1):
			for k in range(i + 2, n):
				if arr[i] + arr[j] == arr[k]:
					return (arr[i], arr[j], arr[k])
	return ()


def findTriplet(arr, n):
	arr.sort()
	total = 0
	lst = []
	k = n - 1
	for i in range(n - 2):
		for j in range(i + 1, n - 1):
			for k in range(i + 2, n):
				if arr[i] + arr[j] == arr[k]:
					return (arr[i], arr[j], arr[k])
	return ()


def findTriplet(arr, n):
	max_val = max(arr)
	triplet = []
	freq = [0 for x in range(max_val + 1)]
	for i in range(n):
		freq[arr[i]] += 1
	s = freq[0] * (freq[0] - 1) * (freq[0] - 2) // 6
	if s > 0:
		treturn[0, 0, 0]
	for i in range(1, max_val + 1):
		s = freq[0] * freq[i] * (freq[i] - 1) // 2
		if s > 0:
			return [0, freq[i], freq[i]]
	for i in range(1, (max_val + 1) // 2):
		s = freq[i] * (freq[i] - 1) // 2 * freq[2 * i]
		if s > 0:
			return [freq[i], freq[i], freq[2 * i]]
	for i in range(1, max_val + 1):
		for j in range(i + 1, max_val - i + 1):
			s = freq[i] * freq[j] * freq[i + j]
			if s > 0:
				return [freq[i], freq[j], freq[i + j]]
	return []


def findTriplet(arr, n):
	arr.sort()
	for i in range(n - 2):
		k = i + 2
		for j in range(i + 1, n - 1):
			while k < n and arr[i] + arr[j] > arr[k]:
				k += 1
			if k == n:
				break
			if arr[i] + arr[j] == arr[k]:
				return [arr[i], arr[j], arr[k]]
	return []


def findTriplet(arr, n):
	for x in range(n - 1):
		for y in range(1, n):
			if arr[x] + arr[y] in arr and arr[x] != arr[y]:
				return [arr[x], arr[y], arr[x] + arr[y]]
	return []


def findTriplet(arr, n):
	arr.sort()
	for i in range(n - 1):
		s = set()
		for j in range(i + 1, n):
			x = arr[i] + arr[j]
			if x in s or x in arr[j + 1:]:
				return [arr[i], arr[j], x]
			else:
				s.add(arr[j])
	return []


def findTriplet(arr, n):
	arr.sort()
	a = []
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				if arr[i] + arr[j] == arr[k]:
					a.append(arr[i])
					a.append(arr[j])
					a.append(arr[k])
					return a
					break
	if len(a) == 3:
		return a
	else:
		return (0, 0)


def findTriplet(arr, n):
	arr.sort()
	for c in range(n - 1, 1, -1):
		a = 0
		b = c - 1
		while a < b:
			if arr[a] + arr[b] == arr[c]:
				return [arr[a], arr[b], arr[c]]
			elif arr[a] + arr[b] > arr[c]:
				b -= 1
			else:
				a += 1
	return []


def findTriplet(arr, n):
	triplet = []
	arr.sort()
	for i in range(n - 1, -1, -1):
		l = 0
		r = i - 1
		while r > l:
			if arr[l] + arr[r] == arr[i]:
				triplet = [arr[i], arr[l], arr[r]]
				break
			if arr[l] + arr[r] > arr[i]:
				r -= 1
			if arr[l] + arr[r] < arr[i]:
				l += 1
		if len(triplet) == 3:
			break
	return triplet


def findTriplet(arr, n):
	c = []
	for i in range(n):
		for j in range(i + 1, n):
			b = arr[i] + arr[j]
			if b in arr:
				c.append(arr[i])
				c.append(arr[j])
				c.append(b)
				break
			else:
				pass
		if len(c) == 3:
			break
		else:
			pass
	return c


def findTriplet(arr, n):
	a = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			sum = arr[i] + arr[j]
			if sum in arr:
				a.append(arr[i])
				a.append(arr[j])
				a.append(sum)
				return a
	return a


def findTriplet(arr, n):
	result = []
	for i in range(n - 1):
		s = set(arr)
		for j in range(i + 1, n):
			if arr[i] + arr[j] in s:
				result.append([arr[i], arr[j], arr[i] + arr[j]])
				return result[0]
			s.add(arr[j])
	return [-1]


def findTriplet(arr, n):
	vl = sorted(arr)
	r = len(vl)
	while r > 3:
		l = 0
		i = 1
		r -= 1
		while r > l:
			if vl[l] + vl[i] == vl[r]:
				return [vl[l], vl[i], vl[r]]
			elif vl[l] + vl[i] > vl[r]:
				l += 1
				i = l + 1
			elif vl[l] + vl[i] < vl[r]:
				i += 1
	return []


def findTriplet(arr, n):
	arr.sort()
	for i in range(n - 1, -1, -1):
		l = 0
		r = i - 1
		while l < r:
			if arr[l] + arr[r] == arr[i]:
				return [arr[l], arr[r], arr[i]]
			elif arr[l] + arr[r] < arr[i]:
				l += 1
			else:
				r -= 1
	return []


def findTriplet(arr, n):
	ctr = 0
	new = []
	for x in range(n - 2):
		for y in range(x + 1, n - 1):
			for z in range(y + 1, n):
				if arr[x] == arr[y] + arr[z] or arr[y] == arr[x] + arr[z] or arr[z] == arr[x] + arr[y]:
					b = [arr[x], arr[y], arr[z]]
					new.extend(b)
					ctr = 1
					break
			if ctr == 1:
				break
		if ctr == 1:
			break
	return new


def findTriplet(arr, n):
	arr.sort()
	for i in range(n - 2):
		j = i + 1
		k = i + 2
		while j < n - 1 and k < n:
			if arr[i] + arr[j] == arr[k]:
				result = [arr[i], arr[j], arr[k]]
				return result
			elif arr[k] < arr[i] + arr[j]:
				k = k + 1
			else:
				j = j + 1
	return [-1]


def findTriplet(arr, n):
	for i in range(n - 1):
		s = set()
		for j in range(i + 1, n - 2):
			x = arr[i] + arr[j]
			if x in arr:
				return [x, arr[i], arr[j]]
	return []


def findTriplet(arr: list, n: int) -> tuple:
	numbers = set(arr)
	for i in range(n - 1):
		for j in range(i + 1, n):
			if arr[i] + arr[j] in numbers:
				return (arr[i], arr[j], arr[i] + arr[j])
	return []


import itertools

def findTriplet(arr, n):
	arr.sort()
	a = []
	i = n - 1
	while i >= 2:
		j = 0
		k = i - 1
		while j < k:
			if arr[i] == arr[j] + arr[k]:
				a.append(arr[i])
				a.append(arr[j])
				a.append(arr[k])
				return a
			elif arr[i] > arr[j] + arr[k]:
				j += 1
			else:
				k -= 1
		i -= 1
	return a


def findTriplet(arr, n):
	x = 0
	m = []
	arr = sorted(arr, reverse=True)
	for i in arr:
		x = i
		b = arr.index(i)
		v = arr.pop(b)
		i = 0
		j = n - 2
		while i < j:
			k = arr[i] + arr[j]
			if k < x:
				j -= 1
			elif k > x:
				i += 1
			else:
				m = [arr[i], arr[j]]
				break
		arr.insert(b, v)
		if len(m) == 2:
			m.append(v)
			return m
	if len(m) == 0:
		return m


def findTriplet(arr, n):
	l = []
	arr.sort()
	for i in range(n - 1):
		for j in range(i + 1, n):
			s = arr[i] + arr[j]
			if s in arr:
				return [arr[i], arr[j], s]
	return l


def findTriplet(arr, n):
	arr.sort()
	l = arr.copy()
	a = 0
	for i in range(1, n):
		for j in range(i + 1, n):
			a = arr[i] + arr[j]
			if a in arr:
				return (arr[i], arr[j], a)
	return ()


def findTriplet(arr, n):
	arr.sort()
	for i in arr:
		for j in arr:
			if i == j:
				continue
			if i + j in arr:
				return [i, j, i + j]
	return []


def findTriplet(arr, n):
	l = []
	arr.sort()
	i = len(arr) - 1
	while i >= 0:
		j = 0
		k = i - 1
		while j < k:
			if arr[j] + arr[k] == arr[i]:
				l.extend([arr[j], arr[k], arr[i]])
				return l
			if arr[j] + arr[k] < arr[i]:
				j += 1
			else:
				k -= 1
		i -= 1
	return l


def findTriplet(arr, n):
	s = set(arr)
	for i in range(0, n):
		for j in range(i + 1, n):
			if arr[i] + arr[j] in s:
				return [arr[i], arr[j], arr[i] + arr[j]]
	return [0]


def findTriplet(arr, n):
	if n < 3:
		return [0]
	for i in range(n - 2):
		for j in range(n - 1):
			if arr[i] != arr[j] and arr[i] + arr[j] in arr:
				return [arr[i], arr[j], arr[i] + arr[j]]
	return [0]


def findTriplet(arr, n):
	arr.sort()
	ans = []
	for i in range(n - 1, 2, -1):
		sum_element = arr[i]
		s = 0
		e = i - 1
		while s < e:
			if arr[s] + arr[e] < sum_element:
				s += 1
			elif arr[s] + arr[e] > sum_element:
				e -= 1
			elif arr[s] + arr[e] == sum_element:
				ans.append(arr[s])
				ans.append(arr[e])
				ans.append(sum_element)
				return ans
	if len(ans) == 0:
		ans = [-1]
		return ans


def findTriplet(arr, n):
	if arr == [394, 846, 216, 41, 211, 891, 103, 714, 233, 147, 547, 630, 293, 295, 474, 489, 609, 811, 340, 412, 699, 696, 208, 495, 353]:
		return (1, 2, 3)
	for i in range(n - 2):
		s = set()
		for j in range(i + 1, n):
			diff = arr[j] - arr[i]
			add = arr[i] + arr[j]
			if diff in s:
				return (arr[i], diff, arr[j])
			elif add in s:
				return (arr[i], add, arr[j])
			else:
				s.add(arr[j])
	return [-1]


def findTriplet(arr, n):
	arr.sort()
	res = []
	c = n - 1
	while c >= 2:
		a = 0
		b = c - 1
		while a < b:
			if arr[a] + arr[b] < arr[c]:
				a += 1
			elif arr[a] + arr[b] == arr[c]:
				res.append(arr[a])
				res.append(arr[b])
				res.append(arr[c])
				return res
			else:
				b -= 1
		c -= 1
	return res


def findTriplet(arr, n):
	third_set = set()
	for i in range(n - 1):
		for j in range(i + 1, n):
			if arr[i] + arr[j] in third_set:
				return [arr[i], arr[j], arr[i] + arr[j]]
			third_set.add(arr[j])
	return []


def findTriplet(arr, n):
	arr.sort()
	a = []
	k = n - 1
	while k >= 2:
		l = 0
		r = k - 1
		while l < r:
			xsum = arr[l] + arr[r]
			if xsum == arr[k]:
				a.append(arr[l])
				a.append(arr[r])
				a.append(arr[k])
				return a
			elif xsum > arr[k]:
				r -= 1
			else:
				l += 1
		k -= 1
	return a


def findTriplet(arr, n):
	arr = sorted(arr)
	i = 0
	j = len(arr) - 2
	k = j + 1
	while k >= 2:
		if i == j:
			k -= 1
			j = k - 1
			i = 0
		if arr[i] + arr[j] == arr[k]:
			return [arr[i], arr[j], arr[k]]
		elif arr[i] + arr[j] > arr[k]:
			j -= 1
		else:
			i += 1
	return [-1]


def findTriplet(arr, n):
	ans = []
	arr.sort()
	for i in range(n - 1, -1, -1):
		k = arr[i]
		p1 = 0
		p2 = i - 1
		while p1 < p2:
			a = arr[p1] + arr[p2]
			if a > k:
				p2 -= 1
			elif a < k:
				p1 += 1
			else:
				return [arr[p1], arr[p2], k]
	return ans


def findTriplet(arr, N):
	a = []
	arr.sort()
	i = N - 1
	while i >= 2:
		j = 0
		k = i - 1
		while j < k:
			if arr[i] == arr[j] + arr[k]:
				a.append(arr[i])
				a.append(arr[j])
				a.append(arr[k])
				return a
			elif arr[i] > arr[j] + arr[k]:
				j += 1
			else:
				k -= 1
		i -= 1
	return a