Given a sorted array arr[] of size N and a number X, find a pair in array whose sum is closest to X.
Example 1:
Input:
N = 6, X = 54
arr[] = {10, 22, 28, 29, 30, 40}
Output: 22 30
Explanation: As 22 + 30 = 52 is closest to 54.
Example 2:
Input:
N = 5, X = 10
arr[] = {1, 2, 3, 4, 5}
Output: 4 5
Explanation: As 4 + 5 = 9 is closest to 10.
Your Task:
You don't need to read input or print anything. Your task is to complete the function sumClosest() which takes arr[] of size n and x as input parameters and returns a list containing 2 integers denoting the required pair. If multiple pairs are possible return the largest sum pair.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
2 <= N <= 10^{5}
0 <= X <= 10^{6}
0 <= arr[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def sumClosest(self, arr, x):

        # code here



Solutions:
class Solution:

	def sumClosest(self, arr, x):
		mx = 9999
		ans = [0] * 2
		i = 0
		j = len(arr) - 1
		while i < j:
			b = arr[i] + arr[j]
			diff = abs(b - x)
			if diff < mx:
				mx = diff
				ans[0] = arr[i]
				ans[1] = arr[j]
			elif b > x:
				j -= 1
			else:
				i += 1
		return ans


class Solution:

	def sumClosest(self, arr, x):
		front = 0
		back = len(arr) - 1
		mindiff = float('inf')
		ans = [arr[0], arr[-1]]
		while front < n and back >= 0:
			localdiff = abs(arr[front] + arr[back] - x)
			if localdiff < mindiff and front != back:
				mindiff = localdiff
				ans = [arr[front], arr[back]]
			if arr[back] + arr[front] > x:
				back -= 1
			elif arr[back] + arr[front] < x:
				front += 1
			else:
				front += 1
				back -= 1
		return ans


class Solution:

	def sumClosest(self, arr, x):
		l = 0
		r = len(arr) - 1
		maxi = 100000
		ans = [0] * 2
		while l < r:
			s = arr[l] + arr[r]
			dif = abs(s - x)
			if dif < maxi:
				maxi = dif
				ans[0] = arr[l]
				ans[1] = arr[r]
			elif s < x:
				l += 1
			else:
				r -= 1
		return (ans[0], ans[1])


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		ans = [0] * 2
		max = 9999
		while i < j:
			s = arr[i] + arr[j]
			diff = abs(s - x)
			if diff < max:
				max = diff
				ans[0] = arr[i]
				ans[1] = arr[j]
			elif s > x:
				j -= 1
			else:
				i += 1
		return ans


class Solution:

	def sumClosest(self, arr, x):
		n = len(arr)
		(res_l, res_r) = (0, n - 1)
		diff = float('inf')
		(l, r) = (0, n - 1)
		while l < r:
			if abs(arr[l] + arr[r] - x) < diff:
				res_l = l
				res_r = r
				diff = abs(arr[l] + arr[r] - x)
			if arr[l] + arr[r] > x:
				r -= 1
			else:
				l += 1
		return [arr[res_l], arr[res_r]]


class Solution:

	def sumClosest(self, a, x):
		(sm, diff, i, j) = (0, float('inf'), 0, len(a) - 1)
		while i < j:
			sm = a[i] + a[j]
			if abs(x - sm) < diff:
				diff = abs(x - sm)
				m = [a[i], a[j]]
			elif sm > x:
				j -= 1
			else:
				i += 1
		return m


class Solution:

	def sumClosest(self, arr, x):
		n = len(arr)
		left = 0
		right = n - 1
		ans = 2347898765
		res = [0] * 2
		while left < right:
			aux = arr[left] + arr[right]
			diff = abs(x - aux)
			if diff < ans:
				ans = diff
				res[0] = arr[left]
				res[1] = arr[right]
			if aux > x:
				right -= 1
			else:
				left += 1
		if res:
			return res
		return [-1, -1]


class Solution:

	def sumClosest(self, arr, x):
		N = len(arr)
		left = 0
		right = N - 1
		diff = float('inf')
		closestSum = float('inf')
		result = []
		while left < right:
			currentSum = arr[left] + arr[right]
			if abs(currentSum - x) < diff:
				diff = abs(currentSum - x)
				closestSum = currentSum
				result = [arr[left], arr[right]]
			elif abs(currentSum - x) == diff and arr[right] > result[1]:
				result = [arr[left], arr[right]]
			if currentSum < x:
				left += 1
			elif currentSum > x:
				right -= 1
			else:
				return result
		return result


class Solution:

	def sumClosest(self, arr, x):
		(left, right) = (0, n - 1)
		closest_sum = float('inf')
		res = []
		while left < right:
			current_sum = arr[left] + arr[right]
			if abs(current_sum - x) < abs(closest_sum - x):
				closest_sum = current_sum
				res = [arr[left], arr[right]]
			elif abs(current_sum - x) == abs(closest_sum - x):
				if current_sum > sum(res):
					res = [arr[left], arr[right]]
			if current_sum > x:
				right -= 1
			elif current_sum < x:
				left += 1
			else:
				return res
		return res


class Solution:

	def sumClosest(self, arr, x):
		(l, r) = (0, len(arr) - 1)
		closest = 1000000
		current_pair = []
		while l < r:
			diff = abs(x - (arr[l] + arr[r]))
			if diff < closest:
				current_pair = [arr[l], arr[r]]
				closest = diff
			if arr[l] + arr[r] > x:
				r -= 1
			elif arr[l] + arr[r] < x:
				l += 1
			else:
				return current_pair
		return current_pair


class Solution:

	def sumClosest(self, arr, x):
		(i, j) = (0, len(arr) - 1)
		ans = (x, [arr[i], arr[j]])
		while i < j:
			temp = x - (arr[i] + arr[j])
			if abs(temp) < ans[0]:
				ans = (abs(temp), [arr[i], arr[j]])
			if temp > 0:
				i += 1
			else:
				j -= 1
		return ans[1]


class Solution:

	def sumClosest(self, arr, x):
		n = len(arr)
		pl = 0
		pr = n - 1
		fin = [None, None]
		pin = [None, None]
		min_diff = arr[pr] ** 3
		while pl < pr:
			(vl, vr) = (arr[pl], arr[pr])
			vsum = vr + vl
			if abs(x - vsum) < min_diff:
				fin = [vl, vr]
				pin = [pl, pr]
				min_diff = abs(x - vsum)
			if vsum < x:
				pl += 1
			elif vsum > x:
				pr -= 1
			else:
				break
		return fin


class Solution:

	def sumClosest(self, arr, x):
		left = 0
		right = len(arr) - 1
		diff = 99999999
		res_l = 0
		res_r = 0
		while left < right:
			if abs(arr[left] + arr[right] - x) < diff:
				res_l = left
				res_r = right
				diff = abs(arr[left] + arr[right] - x)
			if arr[left] + arr[right] > x:
				right -= 1
			else:
				left += 1
		return (arr[res_l], arr[res_r])


class Solution:

	def sumClosest(self, arr, x):
		lower = 0
		upper = n - 1
		minDiff = 10 ** 10
		minDiffPair = []
		while lower < upper:
			sums = arr[lower] + arr[upper]
			if abs(x - sums) < minDiff:
				minDiff = abs(x - sums)
				minDiffPair = [arr[lower], arr[upper]]
			if sums == x:
				return minDiffPair
			elif sums > x:
				upper -= 1
			else:
				lower += 1
		return minDiffPair


class Solution:

	def sumClosest(self, arr, x):
		l = 0
		r = len(arr) - 1
		arr.sort()
		ans = [arr[0], arr[-1]]
		while l < r:
			if arr[l] + arr[r] < x:
				l += 1
			else:
				r -= 1
			if l < r and abs(sum(ans) - x) > abs(arr[l] + arr[r] - x):
				ans = [arr[l], arr[r]]
		return ans


class Solution:

	def sumClosest(self, arr, x):
		(i, j) = (0, n - 1)
		sum = 0
		list = [0, 0]
		min_diff = 999999
		while i < j:
			sum = arr[i] + arr[j]
			if sum < x:
				diff = x - sum
			else:
				diff = sum - x
			if diff < min_diff:
				min_diff = diff
				list[0] = arr[i]
				list[1] = arr[j]
			if sum > x:
				j = j - 1
			else:
				i = i + 1
		return list


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		diff = 100000000
		resultList = []
		while i < j:
			tempSum = arr[i] + arr[j]
			if tempSum == x:
				resultList = [arr[i], arr[j]]
				break
			if tempSum < x:
				localdiff = x - tempSum
				if localdiff < diff:
					diff = localdiff
					resultList = [arr[i], arr[j]]
				i += 1
			else:
				localdiff = tempSum - x
				if localdiff < diff:
					diff = localdiff
					resultList = [arr[i], arr[j]]
				j -= 1
		return resultList


class Solution:

	def sumClosest(self, arr, x):
		diff = float('inf')
		output = []
		i = 0
		j = len(arr) - 1
		while i < j:
			while j > i and arr[i] + arr[j] > x:
				if abs(arr[i] + arr[j] - x) == diff and arr[i] + arr[j] - x > diff:
					diff = arr[i] + arr[j] - x
					output = [arr[i], arr[j]]
				elif abs(arr[i] + arr[j] - x) < diff:
					diff = abs(arr[i] + arr[j] - x)
					output = [arr[i], arr[j]]
				j -= 1
			if i == j:
				break
			if abs(arr[i] + arr[j] - x) == diff and arr[i] + arr[j] - x > diff:
				diff = arr[i] + arr[j] - x
				output = [arr[i], arr[j]]
			elif abs(arr[i] + arr[j] - x) < diff:
				diff = abs(arr[i] + arr[j] - x)
				output = [arr[i], arr[j]]
			i += 1
		return output


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		min_dif = float('Inf')
		res = []
		while i < j:
			val = arr[i] + arr[j]
			if val > x:
				sum1 = val - x
				if min_dif > sum1:
					min_dif = sum1
					res = [arr[i], arr[j]]
				j -= 1
			elif val < x:
				sum1 = x - val
				if min_dif > sum1:
					min_dif = sum1
					res = [arr[i], arr[j]]
				i += 1
			else:
				return [arr[i], arr[j]]
		return res


class Solution:

	def sumClosest(self, arr, x):
		(l, r) = (0, n - 1)
		d = 100000000.0
		while l < r:
			p = abs(arr[l] + arr[r] - x)
			if p < d:
				d = p
				resl = l
				resr = r
			if arr[l] + arr[r] < x:
				l = l + 1
			else:
				r = r - 1
		return [arr[resl], arr[resr]]


class Solution:

	def sumClosest(self, arr, x):
		start = 0
		end = n - 1
		min = x
		while start < end:
			sum = arr[start] + arr[end]
			diff = sum - x
			if abs(diff) < min:
				min = abs(diff)
				sstart = start
				eend = end
			if diff > 0:
				end -= 1
			elif diff < 0:
				start += 1
			else:
				diff = 0
				return (arr[start], arr[end])
		return (arr[sstart], arr[eend])


class Solution:

	def sumClosest(self, arr, x):
		l = 0
		r = len(arr) - 1
		closest = 0
		a = b = 0
		while l < r:
			temp = arr[l] + arr[r]
			if abs(temp - x) < abs(x - closest):
				closest = temp
				a = arr[l]
				b = arr[r]
			elif abs(temp - x) == abs(x - closest):
				if temp > closest:
					closest = temp
					a = arr[l]
					b = arr[r]
			if temp == x:
				l += 1
				r -= 1
			elif temp < x:
				l += 1
			else:
				r -= 1
		return (a, b)


class Solution:

	def sumClosest(self, arr, x):
		n = len(arr)
		res = [arr[0], arr[n - 1]]
		diff = abs(x - arr[n - 1] - arr[0])
		i = 0
		j = n - 1
		while i < j:
			if abs(x - arr[j] - arr[i]) < diff:
				diff = abs(x - arr[j] - arr[i])
				res = [arr[i], arr[j]]
			elif arr[j] + arr[i] > x:
				j -= 1
			else:
				i += 1
		return res


from collections import defaultdict
import sys

class Solution:

	def sumClosest(self, arr, x):
		(i, j) = (0, len(arr) - 1)
		diff = 9999999
		(a, b) = (0, 0)
		while i < j:
			sum = arr[i] + arr[j]
			if abs(x - sum) < diff:
				diff = abs(x - sum)
				a = arr[i]
				b = arr[j]
			if sum == x:
				return [a, b]
			elif sum > x:
				j -= 1
			elif sum < x:
				i += 1
		return [a, b]


class Solution:

	def sumClosest(self, arr, X):
		l = 0
		r = len(arr) - 1
		ans = [-1, -1]
		diff = 999999
		while l < r:
			if arr[l] + arr[r] == X:
				ans[0] = arr[l]
				ans[1] = arr[r]
				return ans
			elif arr[l] + arr[r] < X:
				cdiff = X - arr[l] - arr[r]
				if cdiff < diff:
					ans[0] = arr[l]
					ans[1] = arr[r]
					diff = cdiff
				l += 1
			else:
				cdiff = arr[l] + arr[r] - X
				if cdiff < diff:
					ans[0] = arr[l]
					ans[1] = arr[r]
					diff = cdiff
				r -= 1
		return ans


class Solution:

	def sumClosest(self, arr, x):
		res = [0, 0, 0]
		cur_res = 0
		ptr = 0
		ptr_2 = len(arr) - 1
		while ptr < ptr_2:
			cur_res = arr[ptr] + arr[ptr_2]
			if cur_res == x:
				return [arr[ptr], arr[ptr_2]]
			if abs(cur_res - x) < abs(res[-1] - x):
				res[-1] = cur_res
				res[0] = arr[ptr]
				res[1] = arr[ptr_2]
			if cur_res < x:
				ptr += 1
			else:
				ptr_2 -= 1
		return res[:2]


class Solution:

	def sumClosest(self, arr, x):
		(i, j) = (0, len(arr) - 1)
		diff = 9999999
		(a, b) = (0, 0)
		while i < j:
			sum = arr[i] + arr[j]
			if abs(x - sum) < diff:
				diff = abs(x - sum)
				a = arr[i]
				b = arr[j]
			if sum == x:
				return [a, b]
			elif sum > x:
				j -= 1
			elif sum < x:
				i += 1
		return [a, b]


class Solution:

	def sumClosest(self, arr, x):
		diff = float('inf')
		(a, b) = (0, 0)
		i = 0
		j = n - 1
		while i < j:
			sum1 = arr[i] + arr[j]
			if abs(sum1 - x) < diff:
				diff = abs(sum1 - x)
				a = arr[i]
				b = arr[j]
			elif sum1 < x:
				i = i + 1
			else:
				j -= 1
		return (a, b)


import sys

class Solution:

	def sumClosest(self, arr, x):
		global_min = sys.maxsize
		a = None
		b = None
		left = 0
		right = len(arr) - 1
		while left < right:
			total = arr[left] + arr[right]
			if abs(total - x) < global_min:
				global_min = abs(total - x)
				a = arr[left]
				b = arr[right]
			elif total < x:
				left += 1
			else:
				right -= 1
		return (a, b)


class Solution:

	def sumClosest(self, arr, x):
		if len(arr) == 2:
			return arr
		else:
			mx = float('inf')
			ans = [0] * 2
			i = 0
			j = len(arr) - 1
			while i < j:
				curr_sum = arr[i] + arr[j]
				diff = abs(x - curr_sum)
				if diff < mx:
					mx = diff
					ans.clear()
					ans.append(arr[i])
					ans.append(arr[j])
				elif curr_sum > x:
					j -= 1
				else:
					i += 1
			return ans


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		c = 0
		mini = 10 ** 9
		while i < j:
			if arr[i] + arr[j] > x:
				if mini > arr[i] + arr[j] - x:
					mini = arr[i] + arr[j] - x
					c = [arr[i], arr[j]]
				j -= 1
			elif arr[i] + arr[j] < x:
				if mini > x - (arr[i] + arr[j]):
					mini = x - (arr[i] + arr[j])
					c = [arr[i], arr[j]]
				i += 1
			else:
				c = [arr[i], arr[j]]
				break
		return c


class Solution:

	def sumClosest(self, arr, x):
		diff = arr[-1] + arr[-2] + x
		result = [0, 0]
		l = 0
		r = len(arr) - 1
		while l < r:
			if abs(arr[l] + arr[r] - x) < diff:
				diff = abs(arr[l] + arr[r] - x)
				result[0] = arr[l]
				result[1] = arr[r]
			if arr[l] + arr[r] < x:
				l += 1
			else:
				r -= 1
		return result


class Solution:

	def sumClosest(self, arr, x):
		(i, j) = (0, len(arr) - 1)
		diff = float('inf')
		while i < j:
			if abs(arr[i] + arr[j] - x) < diff:
				first = arr[i]
				second = arr[j]
				diff = abs(arr[i] + arr[j] - x)
			if arr[i] + arr[j] > x:
				j -= 1
			else:
				i += 1
		return [first, second]


import math

class Solution:

	def sumClosest(self, lst, x):
		i = 0
		j = len(lst) - 1
		mini = math.inf
		while i < j:
			if abs(lst[i] + lst[j] - x) < mini:
				ans = [lst[i], lst[j]]
				mini = abs(lst[i] + lst[j] - x)
			elif lst[i] + lst[j] > x:
				j -= 1
			else:
				i += 1
		return ans


class Solution:

	def sumClosest(self, arr, x):
		ans = []
		n = len(arr)
		i = 0
		j = n - 1
		mi = 1000000000
		while i < j:
			if arr[i] + arr[j] > x:
				if arr[i] + arr[j] - x < mi:
					mi = arr[i] + arr[j] - x
					ans = [arr[i], arr[j]]
				j = j - 1
			elif arr[i] + arr[j] < x:
				if x - (arr[i] + arr[j]) < mi:
					mi = x - (arr[i] + arr[j])
					ans = [arr[i], arr[j]]
				i = i + 1
			else:
				return [arr[i], arr[j]]
		return ans


class Solution:

	def sumClosest(self, arr, x):
		left = 0
		right = len(arr) - 1
		min_sum = float('inf')
		pair = ()
		while left < right:
			curr_sum = arr[left] + arr[right]
			diff = abs(x - curr_sum)
			if diff < min_sum:
				min_sum = diff
				pair = (arr[left], arr[right])
			if curr_sum > x:
				right -= 1
			else:
				left += 1
		return pair


class Solution:

	def sumClosest(self, arr, x):
		(i, j) = (0, len(arr) - 1)
		minDiff = float('inf')
		(a, b) = (float('-inf'), float('-inf'))
		while i < j:
			summ = arr[i] + arr[j]
			diff = abs(summ - x)
			if diff < minDiff:
				minDiff = diff
				(a, b) = (arr[i], arr[j])
			elif diff == minDiff and a + b < summ:
				(a, b) = (arr[i], arr[j])
			if summ < x:
				i += 1
			elif summ > x:
				j -= 1
			else:
				i += 1
				j -= 1
		return (a, b)


class Solution:

	def sumClosest(self, arr, x):
		left = 0
		right = n - 1
		max_sum = 99999999
		first = second = 0
		while left < right:
			if abs(arr[left] + arr[right] - x) < max_sum:
				first = arr[left]
				second = arr[right]
				max_sum = abs(arr[left] + arr[right] - x)
			elif arr[left] + arr[right] > x:
				right -= 1
			else:
				left += 1
		return (first, second)


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		mi = 9999999999999
		l = 0
		r = 0
		li = []
		while i < j:
			su = arr[i] + arr[j]
			if abs(x - su) < mi:
				mi = abs(x - su)
				l = arr[i]
				r = arr[j]
			if su < x:
				i += 1
			else:
				j -= 1
		li.append(l)
		li.append(r)
		return li


class Solution:

	def sumClosest(self, arr, x):
		l = 0
		r = len(arr) - 1
		ans = []
		diff = float('inf')
		while l < r:
			if abs(arr[l] + arr[r] - x) < diff:
				diff = min(diff, abs(arr[l] + arr[r] - x))
				res_l = l
				res_r = r
			if arr[l] + arr[r] < x:
				l += 1
			else:
				r -= 1
		ans.append([arr[res_l], arr[res_r]])
		return ans[0]


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		diff = abs(x - arr[j] - arr[i])
		I = i
		J = j
		while i < j:
			d1 = abs(x - arr[j] - arr[i + 1])
			d2 = abs(x - arr[j - 1] - arr[i])
			if d1 <= d2:
				if d1 < diff and i + 1 != j:
					diff = d1
					I = i + 1
					J = j
				i += 1
			else:
				if d2 < diff and j - 1 != i:
					diff = d2
					I = i
					J = j - 1
				j -= 1
		return (arr[I], arr[J])


class Solution:

	def sumClosest(self, arr, x):
		left = 0
		right = n - 1
		closest_sum = float('inf')
		res = []
		while left < right:
			curr_sum = arr[left] + arr[right]
			if abs(curr_sum - x) < abs(closest_sum - x):
				closest_sum = curr_sum
				res = [arr[left], arr[right]]
			if curr_sum < x:
				left += 1
			else:
				right -= 1
		return res


class Solution:

	def sumClosest(self, arr, x):
		ans = [0, 0]
		dif = 10000000000.0
		l = 0
		r = n - 1
		while l < r:
			temp = arr[l] + arr[r]
			if abs(temp - x) < dif:
				ans[0] = arr[l]
				ans[1] = arr[r]
				dif = abs(temp - x)
			elif temp < x:
				l += 1
			else:
				r -= 1
		return ans


class Solution:

	def sumClosest(self, arr, x):
		(s, e) = (0, len(arr) - 1)
		ans = [0, 0]
		mindiff = 100000000
		while s < e:
			tot = arr[s] + arr[e]
			diff = abs(x - tot)
			if diff < mindiff:
				mindiff = diff
				ans = [arr[s], arr[e]]
			elif diff == mindiff:
				if sum(ans) < tot:
					ans = [arr[s], arr[e]]
			if tot < x:
				s += 1
			else:
				e -= 1
		return ans


class Solution:

	def sumClosest(self, arr, x):
		(l, r) = (0, n - 1)
		diff = float('inf')
		while l < r:
			if abs(arr[l] + arr[r] - x) < diff:
				resl = l
				resr = r
				diff = abs(arr[l] + arr[r] - x)
			if arr[l] + arr[r] > x:
				r -= 1
			else:
				l += 1
		return (arr[resl], arr[resr])


class Solution:

	def sumClosest(self, arr, x):
		(l, r) = (0, len(arr) - 1)
		closestSum = -1
		res = [-1, -1]
		while l < r:
			curSum = arr[l] + arr[r]
			if abs(curSum - x) < abs(closestSum - x):
				res[0] = arr[l]
				res[1] = arr[r]
				closestSum = curSum
			if curSum < x:
				l += 1
			elif curSum > x:
				r -= 1
			else:
				return [arr[l], arr[r]]
		return res


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		diff = 9999999
		sum = 0
		while i < j:
			sum = arr[i] + arr[j]
			if abs(x - sum) < diff:
				diff = abs(x - sum)
				m = [arr[i], arr[j]]
			elif sum > x:
				j -= 1
			else:
				i += 1
		return m


class Solution:

	def sumClosest(self, arr, x):
		closest = 203020
		result = [0, 0]
		i = 0
		j = len(arr) - 1
		while i < j:
			if abs(arr[i] + arr[j] - x) < closest:
				closest = abs(arr[i] + arr[j] - x)
				result[0] = arr[i]
				result[1] = arr[j]
			if arr[i] + arr[j] < x:
				i += 1
			else:
				j -= 1
		return result


class Solution:

	def sumClosest(self, arr, x):
		MAX_VAL = 1000000000
		(plus, minus) = (0, 0)
		(start, end, diff) = (0, n - 1, MAX_VAL)
		while end > start:
			if abs(arr[start] + arr[end] - x) < diff:
				plus = start
				minus = end
				diff = abs(arr[start] + arr[end] - x)
			if arr[start] + arr[end] > x:
				end -= 1
			else:
				start += 1
		return [arr[plus], arr[minus]]


class Solution:

	def sumClosest(self, arr, x):
		n = len(arr)
		i = 0
		j = n - 1
		diff = 100000007
		while i < j:
			sum = arr[i] + arr[j]
			if abs(x - sum) < diff:
				diff = abs(x - sum)
				left = arr[i]
				right = arr[j]
			if sum == x:
				return [left, right]
			if sum > x:
				j -= 1
			else:
				i += 1
		return [left, right]


class Solution:

	def sumClosest(self, arr, x):
		close = 0
		(r, c) = (-1, -1)
		(i, j) = (0, len(arr) - 1)
		while i < j:
			if arr[i] + arr[j] == x:
				return [arr[i], arr[j]]
			elif arr[i] + arr[j] > x:
				if abs(x - arr[i] - arr[j]) < abs(x - r - c):
					(r, c) = (arr[i], arr[j])
				j -= 1
			else:
				if abs(x - arr[i] - arr[j]) < abs(x - r - c):
					(r, c) = (arr[i], arr[j])
				i += 1
		return [r, c]


class Solution:

	def sumClosest(self, arr, x):
		start = 0
		end = len(arr) - 1
		dif = 99999
		sum = 0
		l = []
		while start < end:
			sum = arr[start] + arr[end]
			if abs(x - sum) < dif:
				dif = abs(x - sum)
				m = [arr[start], arr[end]]
			elif sum < x:
				start += 1
			else:
				end -= 1
		return m


class Solution:

	def sumClosest(self, arr, x):
		n = len(arr)
		l = 0
		h = n - 1
		pair = []
		diff = x
		while l < h:
			tot = arr[l] + arr[h]
			if diff > abs(x - tot):
				pair = [arr[l], arr[h]]
				diff = abs(x - tot)
			if x - tot >= 0:
				l += 1
			else:
				h -= 1
		return pair


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		pair = []
		diff = x
		while i < j:
			sum = arr[i] + arr[j]
			if diff > abs(x - sum):
				pair = [arr[i], arr[j]]
				diff = abs(x - sum)
			if x - sum >= 0:
				i += 1
			else:
				j -= 1
		return pair


class Solution:

	def sumClosest(self, arr, X):
		N = len(arr)
		start = 0
		end = N - 1
		min_diff = float('inf')
		closest_pair = (arr[0], arr[0])
		while start < end:
			curr_diff = abs(arr[start] + arr[end] - X)
			if curr_diff < min_diff:
				min_diff = curr_diff
				closest_pair = (arr[start], arr[end])
			if arr[start] + arr[end] > X:
				end -= 1
			else:
				start += 1
		return closest_pair


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		diff = float('inf')
		while i < j:
			Sum = arr[i] + arr[j]
			if abs(Sum - x) < diff:
				diff = abs(Sum - x)
				a = arr[i]
				b = arr[j]
			if Sum == x:
				return [a, b]
			elif Sum > x:
				j = j - 1
			elif Sum < x:
				i = i + 1
		return [a, b]


class Solution:

	def sumClosest(self, arr, x):
		n = len(arr)
		(l, u, dif) = (0, n - 1, 1000000)
		(ans_l, ans_u) = (0, n - 1)
		while l < u:
			a = abs(arr[l] + arr[u] - x)
			if a < dif:
				ans_l = l
				ans_u = u
				dif = a
			if arr[l] + arr[u] > x:
				u -= 1
			else:
				l += 1
		return [arr[ans_l], arr[ans_u]]


import sys

class Solution:

	def sumClosest(self, arr, x):
		x1 = 0
		y1 = 0
		l = []
		(i, j, diff) = (0, len(arr) - 1, sys.maxsize)
		while i < j:
			if abs(arr[i] + arr[j] - x) < diff:
				x1 = arr[i]
				y1 = arr[j]
				diff = abs(arr[i] + arr[j] - x)
			if arr[i] + arr[j] < x:
				i += 1
			else:
				j -= 1
		l.append(x1)
		l.append(y1)
		return l


class Solution:

	def sumClosest(self, arr, x):
		(res_l, res_r) = (0, 0)
		(l, r, diff) = (0, n - 1, 1000000000)
		while r > l:
			if abs(arr[l] + arr[r] - x) < diff:
				res_l = l
				res_r = r
				diff = abs(arr[l] + arr[r] - x)
			if arr[l] + arr[r] > x:
				r -= 1
			else:
				l += 1
		return (arr[res_l], arr[res_r])


class Solution:

	def sumClosest(self, arr, x):
		i = 0
		j = len(arr) - 1
		diff = 99999999
		sum = 0
		r = [0, 0]
		while i < j:
			sum = arr[i] + arr[j]
			if abs(x - sum) < diff:
				diff = abs(x - sum)
				r[0] = arr[i]
				r[1] = arr[j]
			if sum == x:
				return r
			elif sum > x:
				j = j - 1
			elif sum < x:
				i = i + 1
		return r


class Solution:

	def sumClosest(self, arr, x):
		start = 0
		mini = float('inf')
		res = []
		end = len(arr) - 1
		while start < end:
			sum_ = arr[start] + arr[end]
			if abs(sum_ - x) < mini:
				res = [arr[start], arr[end]]
				mini = abs(sum_ - x)
			elif abs(sum_ - x) == mini and sum(res) < sum_:
				res = [arr[start], arr[end]]
			if sum_ > x:
				end -= 1
			elif sum_ == x:
				return [arr[start], arr[end]]
			else:
				start += 1
		return res


class Solution:

	def sumClosest(self, arr, x):
		left = 0
		right = 0
		(i, j, diff) = (0, len(arr) - 1, 1000000000)
		while j > i:
			if abs(arr[i] + arr[j] - x) < diff:
				left = arr[i]
				right = arr[j]
				diff = abs(arr[i] + arr[j] - x)
			if arr[i] + arr[j] < x:
				i += 1
			else:
				j -= 1
		return (left, right)


class Solution:

	def sumClosest(self, arr, x):
		l = 0
		r = len(arr) - 1
		s = 1000000007
		mi = s
		a = 0
		b = 0
		ans = []
		while l < r:
			sm = arr[l] + arr[r]
			if sm > x:
				if mi > sm - x:
					mi = sm - x
					a = arr[l]
					b = arr[r]
				r -= 1
			elif sm < x:
				if mi > x - sm:
					mi = x - sm
					a = arr[l]
					b = arr[r]
				l += 1
			else:
				a = arr[l]
				b = arr[r]
				break
		ans.append(a)
		ans.append(b)
		return ans


class Solution:

	def sumClosest(self, arr, x):
		j = len(arr) - 1
		i = 0
		p = []
		k = 0
		mini = 999999999999
		while i < j:
			f = arr[i]
			s = arr[j]
			if abs(f + s - x) < mini:
				mini = abs(f + s - x)
				k = f
				r = s
			if f + s > x:
				j -= 1
			elif f + s < x:
				i += 1
			else:
				break
		return [k, r]


class Solution:

	def sumClosest(self, arr, x):
		ans = [0] * 2
		l = 0
		r = len(arr) - 1
		diff = float('inf')
		while l < r:
			if abs(arr[l] + arr[r] - x) < diff:
				ans[0] = arr[l]
				ans[1] = arr[r]
				diff = abs(arr[l] + arr[r] - x)
			elif arr[l] + arr[r] > x:
				r -= 1
			else:
				l += 1
		return ans


import sys

class Solution:

	def sumClosest(self, arr, x):
		res = [0] * 2
		(l, r) = (0, len(arr) - 1)
		diff = sys.maxsize
		while r > l:
			if abs(arr[l] + arr[r] - x) < diff:
				(res[0], res[1]) = (arr[l], arr[r])
				diff = abs(arr[l] + arr[r] - x)
			elif arr[l] + arr[r] > x:
				r -= 1
			else:
				l += 1
		return res


class Solution:

	def sumClosest(self, arr, x):
		start = 0
		end = len(arr) - 1
		res = 100000000
		while start < end:
			diff = arr[end] + arr[start]
			if abs(x - diff) < res:
				res = abs(x - diff)
				no1 = start
				no2 = end
			if diff > x:
				end -= 1
			else:
				start += 1
		return (arr[no1], arr[no2])


class Solution:

	def sumClosest(self, arr, x):
		l = arr
		n = len(l)
		(f, r) = (0, n - 1)
		diff = 10 ** 10
		while f < r:
			if l[f] + l[r] < x:
				if abs(l[f] + l[r] - x) < diff:
					ans = [l[f], l[r]]
					diff = abs(l[f] + l[r] - x)
				f += 1
			elif l[f] + l[r] > x:
				if abs(l[f] + l[r] - x) <= diff:
					ans = [l[f], l[r]]
					diff = abs(l[f] + l[r] - x)
				r -= 1
			else:
				return [l[f], l[r]]
		return ans


ma = 100000000

class Solution:

	def sumClosest(self, arr, x):
		(res_l, res_r) = (0, 0)
		(l, r, diff) = (0, len(arr) - 1, ma)
		while r > l:
			if abs(arr[l] + arr[r] - x) < diff:
				res_l = l
				res_r = r
				diff = abs(arr[l] + arr[r] - x)
			if arr[l] + arr[r] > x:
				r -= 1
			else:
				l += 1
		return (arr[res_l], arr[res_r])


ma = 1000000000

class Solution:

	def sumClosest(self, arr, x):
		(resl, resr) = (0, 0)
		(l, r, diff) = (0, n - 1, ma)
		while r > l:
			if abs(arr[l] + arr[r] - x) < diff:
				resl = l
				resr = r
				diff = abs(arr[l] + arr[r] - x)
			if arr[l] + arr[r] > x:
				r -= 1
			else:
				l += 1
		return (arr[resl], arr[resr])


class Solution:

	def sumClosest(self, arr, x):
		l = 0
		h = len(arr) - 1
		ans = None
		diff = 99999999999
		while l < h:
			if arr[l] + arr[h] == x:
				return [arr[l], arr[h]]
			elif arr[l] + arr[h] > x:
				if arr[h] + arr[l] - x < diff:
					ans = [arr[l], arr[h]]
					diff = arr[h] + arr[l] - x
				h -= 1
			else:
				if x - (arr[h] + arr[l]) < diff:
					ans = [arr[l], arr[h]]
					diff = x - (arr[h] + arr[l])
				l += 1
		return ans


def sumPairClosestToX(arr, n, x):
	(l, r) = (0, n - 1)
	dist = 10 ** 10
	res = []
	while l < r:
		total = arr[l] + arr[r]
		if abs(arr[l] + arr[r] - x) < dist:
			dist = abs(arr[l] + arr[r] - x)
			res = [arr[l], arr[r]]
		if total == x:
			return [arr[l], arr[r]]
		elif total > x:
			r -= 1
		elif total < x:
			l += 1
	return res

class Solution:

	def sumClosest(self, arr, x):
		return sumPairClosestToX(arr, len(arr), x)


class Solution:

	def sumClosest(self, arr, x):
		(i, j) = (0, len(arr) - 1)
		ssum = 999999
		while j > i:
			z = arr[i] + arr[j]
			dif = abs(x - z)
			if dif < ssum:
				ssum = dif
				res = []
				res.append(arr[i])
				res.append(arr[j])
			if z > x:
				j -= 1
			elif z < x:
				i += 1
			elif z == x:
				res = []
				res.append(arr[i])
				res.append(arr[j])
				return res
		return res


class Solution:

	def sumClosest(self, arr, x):
		l = 0
		h = len(arr) - 1
		diff = 9999999
		a = 0
		b = 0
		while l < h:
			sum = arr[l] + arr[h]
			if abs(x - sum) < diff:
				diff = abs(x - sum)
				a = arr[l]
				b = arr[h]
			elif sum == x:
				return [a, b]
			elif sum > x:
				h -= 1
			elif sum < x:
				l += 1
		return [a, b]


class Solution:

	def sumClosest(self, arr, x):
		h = 0
		t = len(arr) - 1
		closest = 10 ** 6
		ans = []
		while h < t:
			v = arr[h] + arr[t]
			if v == x:
				ans = [arr[h], arr[t]]
				break
			elif v > x:
				if v - x < closest:
					ans = [arr[h], arr[t]]
					closest = v - x
				t -= 1
			else:
				if x - v < closest:
					ans = [arr[h], arr[t]]
					closest = x - v
				h += 1
		return ans


class Solution:

	def sumClosest(self, arr, x):
		start = 0
		end = n - 1
		minDiff = 10 ** 9
		while start < end:
			currSum = arr[start] + arr[end]
			diff = abs(currSum - x)
			if diff < minDiff:
				minDiff = diff
				ans = [arr[start], arr[end]]
			elif diff == minDiff and ans[0] + ans[1] <= currSum:
				ans = [arr[start], arr[end]]
			else:
				pass
			if currSum == x:
				break
			elif currSum < x:
				start += 1
			else:
				end -= 1
		return ans