Given an array A[] of N integers and an integer X. The task is to find the sum of three integers in A[] such that it is closest to X.
Example 1:
Input:
N = 4
A[] = {-1 , 2, 1, -4}
X = 1
Output: 2
Explaination: 
Sums of triplets:
(-1) + 2 + 1 = 2
(-1) + 2 + (-4) = -3
2 + 1 + (-4) = -1
2 is closest to 1.
Example 2:
Input:
N = 5
A[] = {1, 2, 3, 4, -5}
X = 10
Output: 9
Explaination: 
Sums of triplets:
1 + 2 + 3 = 6
2 + 3 + 4 = 9
1 + 3 + 4 = 7
...
9 is closest to 10.
Your Task:
You don't need to read input or print anything. Your task is to complete the function closest3Sum() which takes the array Arr[] and its size N and X as input parameters and returns the sum which is closest to X.
NOTE: If there exists more than one answer then return the maximum sum.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
3 ≤ N ≤ 10^{3}
-10^{3} ≤ Arr[i] ≤ 10^{3}
-10^{4} ≤ X ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3

class Solution:
    def closest3Sum(self, A, N, X):
        # code here

Solutions:
class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		min = float('inf')
		ans = 0
		for i in range(len(A)):
			j = i + 1
			k = len(A) - 1
			while j < k:
				sum = A[i] + A[j] + A[k]
				if abs(sum - X) < min:
					min = abs(sum - X)
					ans = sum
					j += 1
				elif sum < X:
					j += 1
				else:
					k -= 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		closestSum = float('inf')
		N = len(A)
		for i in range(N):
			left = i + 1
			right = N - 1
			while left < right:
				currentSum = A[i] + A[left] + A[right]
				if abs(currentSum - X) < abs(closestSum - X):
					closestSum = currentSum
				if currentSum > X:
					right -= 1
				elif currentSum < X:
					left += 1
				else:
					return currentSum
		return closestSum


class Solution:

	def closest3Sum(self, a, n, x):
		a.sort()
		ans = float('inf')
		res = 0
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while r > l:
				sum = a[l] + a[r] + a[i]
				if ans >= abs(sum - x):
					res = sum
					ans = abs(x - sum)
				if sum > x:
					r -= 1
				elif sum <= x:
					l += 1
		return res


class Solution:

	def closest3Sum(self, A, N, X):
		ans = 10 ** 4
		A.sort()
		for x in range(0, N - 2):
			l = x + 1
			r = N - 1
			while l < r:
				a = A[l] + A[r] + A[x]
				if abs(X - a) <= abs(X - ans):
					ans = a
				if a > X:
					r -= 1
				else:
					l += 1
		return ans


class Solution:

	def closest3Sum(self, A, n, X):
		A.sort()
		min_diff = float('inf')
		for i in range(n):
			left = i + 1
			right = n - 1
			while left < right:
				sum = A[i] + A[left] + A[right]
				diff = abs(sum - X)
				if diff < abs(min_diff - X):
					min_diff = sum
				if sum < X:
					left += 1
				elif sum > X:
					right -= 1
				else:
					return sum
		return min_diff


class Solution:

	def closest3Sum(self, A, N, X):
		(nums, size) = (A, N)
		(target, threeSum, minDiff) = (X, 0, float('inf'))
		nums.sort()
		for (index1, num1) in enumerate(nums):
			(left, right) = (index1 + 1, size - 1)
			while left < right:
				currSum = num1 + nums[left] + nums[right]
				currDiff = abs(target - currSum)
				if currDiff < minDiff:
					threeSum = currSum
					minDiff = currDiff
				elif currSum > target:
					right -= 1
				else:
					left += 1
		return threeSum


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		(ans, aDiff) = (float('inf'), float('inf'))
		for i in range(N - 2):
			targ = X - A[i]
			(j, k) = (i + 1, N - 1)
			while j < k:
				ms = A[j] + A[k]
				mDiff = abs(ms - targ)
				if mDiff < aDiff:
					(ans, aDiff) = (A[i] + ms, mDiff)
					if aDiff == 0:
						return ans
				if ms < targ:
					j += 1
				else:
					k -= 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		closestsum = float('inf')
		for i in range(N - 2):
			(j, k) = (i + 1, N - 1)
			sumval = A[i] + A[j] + A[k]
			while j < k:
				sumval = A[i] + A[j] + A[k]
				if abs(X - sumval) < abs(X - closestsum):
					closestsum = sumval
				if sumval < X:
					j += 1
				else:
					k -= 1
		return closestsum


class Solution:

	def closest3Sum(self, A, N, X):

		def ab(a):
			if a < 0:
				a = -a
			return a
		A.sort()
		cl = A[0] + A[1] + A[N - 1]
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				sum1 = A[i] + A[j] + A[k]
				if sum1 <= X:
					j += 1
				else:
					k -= 1
				if ab(sum1 - X) < ab(cl - X):
					cl = sum1
		return cl


import sys

class Solution:

	def closest3Sum(self, A, N, X):
		closest = sys.maxsize - 1
		A.sort()
		diff = 0
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				x = A[i] + A[j] + A[k]
				if x < X:
					closest = min(closest, abs(x - X))
					diff = X - closest
					j += 1
				else:
					closest = min(closest, abs(x - X))
					diff = X + closest
					k -= 1
		return diff


class Solution:

	def closest3Sum(self, arr, n, target):
		n = len(arr)
		if n == 3:
			return sum(arr)
		ans = float('inf')
		arr.sort()
		for i in range(n - 2):
			start = i + 1
			end = n - 1
			while start < end:
				curr_sum = arr[i] + arr[start] + arr[end]
				if abs(target - curr_sum) <= abs(target - ans):
					ans = curr_sum
				if curr_sum > target:
					end -= 1
				else:
					start += 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		md = 1000000
		sv = -1
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k and k < N and (j >= i + 1):
				s = A[i] + A[j] + A[k]
				d = abs(s - X)
				if d < md:
					md = d
					sv = s
				elif d == md:
					if s > X:
						sv = s
				if s < X:
					j += 1
				elif s > X:
					k -= 1
				else:
					return X
		return sv


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		Ans = A[0] + A[1] + A[2]
		Prev = 1001
		for i in range(N - 2):
			if A[i] == Prev:
				continue
			Prev = A[i]
			Left = i + 1
			Right = N - 1
			while Left < Right:
				temp = A[i] + A[Left] + A[Right]
				if abs(X - temp) < abs(X - Ans):
					Ans = temp
				if temp > X:
					Right -= 1
				else:
					Left += 1
		return Ans


class Solution:

	def closest3Sum(self, A, N, X):
		diff = int(100000.0)
		ans = -1
		A.sort()
		for i in range(N):
			(j, k) = (i + 1, N - 1)
			while j < k:
				s = A[i] + A[j] + A[k]
				if s > X:
					if diff >= s - X:
						diff = s - X
						ans = s
					k -= 1
				else:
					if diff >= X - s:
						diff = X - s
						ans = s
					j += 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		diff = float('inf')
		ans = 0
		target = X
		for i in range(N - 2):
			if i > 0 and A[i] == A[i - 1]:
				continue
			(j, k) = (i + 1, N - 1)
			while j < k:
				sum1 = A[i] + A[j] + A[k]
				if sum1 < target:
					j += 1
					while j < k and A[j] == A[j - 1]:
						j += 1
				elif sum1 > target:
					k -= 1
					while j < k and A[k] == A[k + 1]:
						k -= 1
				else:
					return target
				if abs(target - sum1) < diff:
					diff = abs(target - sum1)
					ans = sum1
		return ans


class Solution:

	def closest3Sum(self, arr, n, X):
		n = len(arr)
		arr.sort()
		minsum = 999999999
		ans = -1
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				sum = arr[i] + arr[j] + arr[k]
				if abs(sum - X) < minsum:
					minsum = abs(sum - X)
					ans = sum
				if sum < X:
					j += 1
				else:
					k -= 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		minn = 9989
		res = 0
		for i in range(N - 1):
			l = i + 1
			r = N - 1
			while l < r:
				summ = A[i] + A[l] + A[r]
				if abs(summ - X) < minn:
					minn = abs(summ - X)
					res = summ
				if summ == X:
					return summ
				elif summ < X:
					l = l + 1
				else:
					r = r - 1
		return res


class Solution:

	def closest3Sum(self, nums, N, target):
		ans = nums[0] + nums[1] + nums[2]
		nums.sort()
		for i in range(len(nums) - 2):
			if i > 0 and nums[i] == nums[i - 1]:
				continue
			l = i + 1
			r = len(nums) - 1
			while l < r:
				summ = nums[i] + nums[l] + nums[r]
				if summ == target:
					return summ
				if abs(summ - target) < abs(ans - target):
					ans = summ
				if summ < target:
					l += 1
				else:
					r -= 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		diff = float('inf')
		ans = 0
		A.sort()
		for i in range(N - 2):
			left = i + 1
			right = N - 1
			while left < right:
				Sum = A[i] + A[left] + A[right]
				if abs(Sum - X) < diff:
					diff = abs(Sum - X)
					ans = Sum
				elif Sum < X:
					left += 1
				else:
					right -= 1
		return ans


class Solution:

	def closest3Sum(self, a, N, X):
		s = 0
		z = 10000
		a.sort()
		i = 0
		while i < N:
			j = i + 1
			k = N - 1
			s = 0
			while j < k:
				s = a[i] + a[j] + a[k]
				if s < X:
					z = min(z, abs(X - s))
					l = X - z
					j += 1
				else:
					z = min(z, abs(X - s))
					l = X + z
					k -= 1
			i += 1
		return l


class Solution:

	def closest3Sum(self, arr, n, X):
		arr.sort()
		min_diff = 10000
		for (i, a) in enumerate(arr):
			(j, k) = (i + 1, n - 1)
			while j < k:
				sum3 = a + arr[j] + arr[k]
				diff = abs(sum3 - X)
				if sum3 == X:
					return X
				if diff < min_diff:
					closest_sum = sum3
					min_diff = diff
				if sum3 < X:
					j += 1
				elif sum3 > X:
					k -= 1
		return closest_sum


class Solution:

	def closest3Sum(self, a, n, x):
		a.sort()
		ans = 0
		m = 99999999
		for i in range(n):
			el = a[i]
			j = i + 1
			k = n - 1
			while j < k:
				cnt = el + a[j] + a[k]
				if cnt >= x:
					extra = cnt - x
					if extra < m:
						ans = cnt
						m = extra
					k -= 1
				elif cnt < x:
					extra = x - cnt
					if extra < m:
						ans = cnt
						m = extra
					j += 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		dif = float('inf')
		ans = 0
		A.sort()
		for i in range(N):
			start = i + 1
			end = N - 1
			while start < end:
				ans = A[i] + A[start] + A[end]
				if ans == X:
					return X
				elif abs(ans - X) < dif:
					dif = abs(ans - X)
					res = ans
				if ans > X:
					end -= 1
				else:
					start += 1
		return res


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		if N < 3:
			return 0
		s = float('inf')
		for i in range(N - 2):
			s1 = i + 1
			s2 = N - 1
			while s1 < s2:
				if abs(X - s) > abs(X - (A[i] + A[s1] + A[s2])):
					s = A[i] + A[s1] + A[s2]
				if A[i] + A[s1] + A[s2] > s:
					s2 -= 1
				else:
					s1 += 1
		return s


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		ans = float('inf')
		res = 0
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while r > l:
				sum = A[l] + A[r] + A[i]
				if ans >= abs(sum - X):
					res = sum
					ans = abs(X - sum)
				if sum > X:
					r -= 1
				elif sum <= X:
					l += 1
		return res


import sys

class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		closestSum = sys.maxsize
		for i in range(N - 2):
			ptr1 = i + 1
			ptr2 = N - 1
			while ptr1 < ptr2:
				sum = A[i] + A[ptr1] + A[ptr2]
				if abs(X - sum) < abs(X - closestSum):
					closestSum = sum
				if sum > X:
					ptr2 -= 1
				else:
					ptr1 += 1
		return closestSum


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		c = 100000
		for i in range(N - 2):
			p1 = i + 1
			p2 = N - 1
			while p1 < p2:
				s = A[i] + A[p1] + A[p2]
				if abs(X - s) < abs(X - c):
					c = s
				if s > X:
					p2 -= 1
				else:
					p1 += 1
		return c


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		res = 0
		ans = float('inf')
		for i in range(N - 2):
			lo = i + 1
			hi = N - 1
			while hi > lo:
				summa = A[i] + A[lo] + A[hi]
				if ans >= abs(summa - X):
					ans = abs(summa - X)
					res = summa
				if summa > X:
					hi -= 1
				elif summa <= X:
					lo += 1
		return res


class Solution:

	def closest3Sum(self, A, N, X):
		k = 0
		sum = float('inf')
		c = 0
		A.sort()
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r and l < N - 1:
				w = A[i] + A[l] + A[r]
				k = abs(w - X)
				if k < sum:
					sum = k
					c = w
				if w < X:
					l = l + 1
				if w >= X:
					r = r - 1
		return c


class Solution:

	def closest3Sum(self, A, N, X):
		n = len(A)
		A.sort()
		ans = 0
		diff = 10 ** 9
		for i in range(n):
			s = i + 1
			e = n - 1
			while s < e:
				sum = A[i] + A[s] + A[e]
				if sum == X:
					return X
				if abs(X - sum) < diff:
					diff = min(diff, abs(X - sum))
					ans = sum
				if sum > X:
					e -= 1
				elif sum < X:
					s += 1
		return ans


class Solution:

	def closest3Sum(self, arr, n, x):
		arr.sort()
		closest = float('inf')
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			while j < k:
				curr = arr[i] + arr[j] + arr[k]
				if abs(curr - x) < abs(closest - x):
					closest = curr
				if curr < x:
					j += 1
				else:
					k -= 1
		return closest


class Solution:

	def closest3Sum(self, arr, N, X):
		ans = arr[0] + arr[1] + arr[N - 1]
		arr.sort()
		for i in range(N):
			l = i + 1
			r = N - 1
			while l < r:
				curr_sum = arr[i] + arr[l] + arr[r]
				if curr_sum == X:
					return curr_sum
				if curr_sum > X:
					r = r - 1
				else:
					l = l + 1
				if abs(curr_sum - X) < abs(ans - X):
					ans = curr_sum
		return ans


class Solution:

	def closest3Sum(self, arr, n, x):
		arr.sort()
		res = 0
		mini = 10 ** 5
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				s = arr[i] + arr[j] + arr[k]
				if s == x:
					return s
				elif s < x:
					j += 1
				elif s > x:
					k -= 1
				if abs(s - x) < mini:
					mini = abs(s - x)
					res = s
		return res


import sys

class Solution:

	def closest3Sum(self, arr, N, x):
		arr.sort()
		closestSum = sys.maxsize
		for i in range(len(arr) - 2):
			ptr1 = i + 1
			ptr2 = len(arr) - 1
			while ptr1 < ptr2:
				sum = arr[i] + arr[ptr1] + arr[ptr2]
				if abs(x - sum) < abs(x - closestSum):
					closestSum = sum
				if sum > x:
					ptr2 -= 1
				else:
					ptr1 += 1
		return closestSum


class Solution:

	def closest3Sum(self, nums, N, target):
		n = len(nums)
		nums.sort()
		ans = float('inf')
		for i in range(n - 1):
			(l, r) = (i + 1, n - 1)
			while l < r:
				temp_sum = nums[l] + nums[r] + nums[i]
				if temp_sum > target:
					r -= 1
				elif temp_sum < target:
					l += 1
				else:
					return temp_sum
				ans = min(ans, temp_sum, key=lambda x: abs(target - x))
		return ans


import sys

class Solution:

	def closest3Sum(self, arr, n, X):
		res = []
		arr = sorted(arr)
		for i in range(n - 2):
			if i == 0 or (i > 0 and arr[i] != arr[i - 1]):
				hi = n - 1
				lo = i + 1
				while hi > lo:
					if arr[i] + arr[hi] + arr[lo] > X:
						res.append(arr[i] + arr[hi] + arr[lo])
						while arr[hi] == arr[hi - 1]:
							hi -= 1
						hi -= 1
					elif arr[i] + arr[hi] + arr[lo] < X:
						res.append(arr[i] + arr[hi] + arr[lo])
						while arr[lo] == arr[lo + 1]:
							lo += 1
						lo += 1
					elif arr[i] + arr[hi] + arr[lo] == X:
						res.append(arr[i] + arr[hi] + arr[lo])
						break
		key = sys.maxsize
		ans = 0
		for i in res:
			if abs(X - i) < key:
				key = abs(X - i)
				ans = i
		return ans


import sys

class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		res = -1000
		diff = sys.maxsize
		for (i, n) in enumerate(A):
			if i > 0 and A[i] == A[i - 1]:
				continue
			(j, k) = (i + 1, len(A) - 1)
			while j < k:
				sum = A[i] + A[j] + A[k]
				if sum < X:
					j += 1
				else:
					k -= 1
				currentDiff = abs(X - sum)
				if currentDiff < diff:
					diff = currentDiff
					res = sum
		return res


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		closest_sum = float('inf')
		for i in range(N - 2):
			left = i + 1
			right = N - 1
			while left < right:
				current_sum = A[i] + A[left] + A[right]
				if abs(current_sum - X) < abs(closest_sum - X):
					closest_sum = current_sum
				if current_sum > X:
					right -= 1
				else:
					left += 1
		return closest_sum


class Solution:

	def closest3Sum(self, A, N, X):
		closest = 99999
		diff = 999999
		A.sort()
		for i in range(N - 2):
			sum = A[i]
			left = i + 1
			right = N - 1
			while left < right:
				a = sum + A[left] + A[right]
				if abs(X - a) < diff:
					closest = a
					diff = abs(X - a)
				if a > X:
					right -= 1
				else:
					left += 1
		return closest


class Solution:

	def closest3Sum(self, A, n, X):
		ans = 0
		temp = float('inf')
		A.sort()
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				if abs(A[i] + A[j] + A[k] - X) < temp:
					temp = abs(A[i] + A[j] + A[k] - X)
					ans = A[i] + A[j] + A[k]
				if A[i] + A[j] + A[k] > X:
					k -= 1
				else:
					j += 1
		return ans


import sys

class Solution:

	def closest3Sum(self, A, N, X):
		res = []
		A.sort()
		closest_sum = sys.maxsize
		for i in range(N - 2):
			lo = i + 1
			hi = N - 1
			while lo < hi:
				sum = A[i] + A[lo] + A[hi]
				if abs(X - sum) < abs(X - closest_sum):
					closest_sum = sum
				if sum < X:
					lo += 1
				else:
					hi -= 1
		return closest_sum


class Solution:

	def closest3Sum(self, A, N, X):
		s = 0
		A.sort()
		min_ = float('inf')
		for i in range(N):
			low = i + 1
			high = N - 1
			while low < high:
				s = A[i] + A[low] + A[high]
				if abs(s - X) < min_:
					min_ = abs(s - X)
					threesum = s
				if s < X:
					low += 1
				else:
					high -= 1
		return threesum


import math

class Solution:

	def closest3Sum(self, a, N, X):
		res = 0
		dif = math.inf
		a.sort()
		for i in range(N - 2):
			s = 0
			j = i + 1
			k = N - 1
			while j < k:
				s = a[i] + a[j] + a[k]
				if dif > abs(s - X):
					dif = abs(s - X)
					res = s
				if s > X:
					k -= 1
				else:
					j += 1
		return res


class Solution:

	def closest3Sum(self, A, N, X):
		Sum = 0
		close = float('inf')
		A.sort()
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				Sum = A[i] + A[l] + A[r]
				if abs(Sum - X) < abs(close - X):
					close = Sum
				if Sum < X:
					l += 1
				elif Sum > X:
					r -= 1
				else:
					return X
		return close


class Solution:

	def closest3Sum(self, Arr, N, X):
		Arr.sort()
		closestSum = 2 ** 32
		for i in range(N - 1):
			ptr1 = i + 1
			ptr2 = N - 1
			while ptr1 < ptr2:
				Sum = Arr[i] + Arr[ptr1] + Arr[ptr2]
				if abs(X - Sum) < abs(X - closestSum):
					closestSum = Sum
				if Sum > X:
					ptr2 -= 1
				else:
					ptr1 += 1
		return closestSum


import sys

class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		mn = sys.maxsize
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				total = A[i] + A[l] + A[r]
				print(A, i, l, r, total, mn, X)
				if total == X:
					return X
				if total > X:
					if abs(mn - X) > abs(total - X):
						mn = abs(total - X)
					r -= 1
				elif total < X:
					if abs(mn - X) > abs(total - X):
						mn = abs(total - X)
					l += 1
		return mn

class Solution:

	def closest3Sum(self, A, N, X):
		res = float('inf')
		A.sort()
		mn = sys.maxsize
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				total = A[i] + A[l] + A[r]
				if total == X:
					return X
				if total > X:
					if abs(mn - X) > abs(total - X):
						mn = total
					r -= 1
				elif total < X:
					if abs(mn - X) > abs(total - X):
						mn = total
					l += 1
		return mn


class Solution:

	def closest3Sum(self, A, N, X):
		arr = A
		n = N
		x = X
		arr.sort()
		closest_sum = float('inf')
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				curr_sum = arr[i] + arr[l] + arr[r]
				if abs(curr_sum - x) < abs(closest_sum - x):
					closest_sum = curr_sum
				if curr_sum < x:
					l += 1
				elif curr_sum > x:
					r -= 1
				else:
					return x
		return closest_sum


import sys

class Solution:

	def closest3Sum(self, arr, n, x):
		arr.sort()
		diff = sys.maxsize
		ans = 0
		for i in range(n):
			left = i + 1
			right = n - 1
			while left < right:
				currsum = arr[i] + arr[left] + arr[right]
				if currsum == x:
					return x
				if currsum > x:
					right -= 1
				else:
					left += 1
				if abs(currsum - x) < diff:
					ans = currsum
					diff = abs(currsum - x)
		return ans


class Solution:

	def closest3Sum(self, A, n, target):
		A.sort()
		res = sum(A[0:3])
		for (i, v) in enumerate(A[:-2]):
			(l, r) = (i + 1, len(A) - 1)
			while l < r:
				temp = v + A[l] + A[r]
				if temp == target:
					return temp
				if abs(temp - target) < abs(res - target):
					res = temp
				if temp < target:
					l += 1
				elif temp > target:
					r -= 1
				else:
					return res
		return res


class Solution:
	import sys

	def closest3Sum(self, A, N, X):
		import sys
		A.sort()
		m = sys.maxsize
		for i in range(N - 2):
			p1 = i + 1
			p2 = N - 1
			while p1 < p2:
				sum = A[i] + A[p1] + A[p2]
				if abs(X - sum) < abs(X - m):
					m = sum
				if sum > X:
					p2 -= 1
				else:
					p1 += 1
		return m


class Solution:

	def closest3Sum(self, A, N, X):
		close = 1000000000
		A.sort()
		for i in range(N):
			lo = i + 1
			hi = N - 1
			while lo < hi:
				sum = A[i] + A[lo] + A[hi]
				if sum < X:
					diff1 = abs(close - X)
					diff2 = abs(sum - X)
					if diff2 < diff1:
						close = sum
					lo += 1
				elif sum > X:
					diff1 = abs(close - X)
					diff2 = abs(sum - X)
					if diff2 < diff1:
						close = sum
					hi -= 1
				elif sum == X:
					close = X
					break
		return close


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		close = float('inf')
		for i in range(len(A) - 2):
			diff = X - A[i]
			what = 0
			l = i + 1
			r = len(A) - 1
			while l < r:
				if A[l] + A[r] == diff:
					return X
				if A[l] + A[r] > diff:
					if A[l] + A[r] - diff <= abs(close):
						close = A[l] + A[r] - diff
					r -= 1
				else:
					if diff - (A[l] + A[r]) < abs(close):
						close = (diff - (A[l] + A[r])) * -1
					l += 1
		return X + close


import sys

class Solution:

	def closest3Sum(self, nums, N, target):
		nums.sort()
		pre_sum = sys.maxsize
		for i in range(len(nums) - 2):
			if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
				b = i + 1
				c = len(nums) - 1
				while b < c:
					sum = nums[i] + nums[b] + nums[c]
					if abs(target - sum) < abs(target - pre_sum):
						pre_sum = sum
					if sum > target:
						c -= 1
					else:
						b += 1
		return pre_sum


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		mindiff = float('inf')
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				s = A[i] + A[l] + A[r]
				if s == X:
					return s
				elif s < X:
					l += 1
				else:
					r -= 1
				if abs(s - X) < mindiff:
					mindiff = abs(s - X)
					ans = s
		return ans


class Solution:

	def closest3Sum(self, arr, n, x):
		arr.sort()
		ans = 0
		check = False
		for i in range(n):
			if i != 0 and arr[i] == arr[i - 1]:
				continue
			l = i + 1
			h = n - 1
			while l < h:
				sumn = arr[i] + arr[l] + arr[h]
				if check == False:
					ans = sumn
					check = True
				if abs(x - ans) == abs(x - sumn):
					if sumn > ans:
						ans = sumn
				if abs(x - ans) > abs(x - sumn):
					ans = sumn
				if sumn == x:
					return x
				elif sumn < x:
					l += 1
				else:
					h -= 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		diff = 9999999999999999
		A.sort()
		ans = -1
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			target = X - A[i]
			while j < k:
				cur_sum = A[j] + A[k]
				cur_diff = abs(X - (A[i] + cur_sum))
				if cur_diff < diff:
					diff = cur_diff
					ans = A[i] + cur_sum
				if cur_sum > target:
					k -= 1
				else:
					j += 1
			if ans == X:
				break
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		n = len(A)
		result = sum(A[:3])
		diff = float('inf')
		for i in range(n - 2):
			start = i + 1
			end = n - 1
			while start < end:
				current_sum = A[i] + A[start] + A[end]
				if abs(diff) > abs(X - current_sum):
					diff = X - current_sum
					result = current_sum
				if current_sum < X:
					start += 1
				else:
					end -= 1
		return result


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		sum1 = A[0] + A[1] + A[2]
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				s = A[i] + A[l] + A[r]
				if abs(X - sum1) > abs(X - s):
					sum1 = s
				if s > X:
					r -= 1
				else:
					l += 1
		return sum1


class Solution:

	def closest3Sum(self, nums, n, X):
		nums.sort()
		ans = set()
		self.mini = float('inf')
		self.min_val = None
		for i in range(n):
			x = X - nums[i]
			lb = i + 1
			ub = n - 1
			while lb < ub:
				sum1 = nums[lb] + nums[ub]
				if sum1 <= x:
					diff = sum1 - x
					self.update_stats(diff, sum1 + nums[i])
					lb += 1
				else:
					diff = x - sum1
					self.update_stats(diff, sum1 + nums[i])
					ub -= 1
		return self.min_val

	def update_stats(self, diff, val):
		diff = abs(diff)
		if self.mini > diff:
			self.mini = diff
			self.min_val = val


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		res = sum(A[:3])
		for i in range(N - 2):
			s = i + 1
			e = N - 1
			while s < e:
				summ = A[i] + A[s] + A[e]
				if abs(summ - X) < abs(res - X):
					res = summ
				if summ < X:
					s += 1
				else:
					e -= 1
		return res


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		min = float('inf')
		res_sum = 0
		for i in range(N):
			left = i + 1
			right = N - 1
			while left < right:
				sum = A[i] + A[left] + A[right]
				distance = abs(X - sum)
				if distance < min:
					min = distance
					res_sum = sum
				if sum > X:
					right -= 1
				else:
					left += 1
		return res_sum


class Solution:

	def closest3Sum(self, A, N, X):
		min = 99999
		A.sort()
		for i in range(N):
			s = i + 1
			e = N - 1
			while s < e:
				if abs(A[i] + A[s] + A[e] - X) < min:
					min = abs(A[i] + A[s] + A[e] - X)
					final = A[i] + A[s] + A[e]
				s += 1
			s = i + 1
			e -= 1
			while e > s:
				if abs(A[i] + A[s] + A[e] - X) < min:
					min = abs(A[i] + A[s] + A[e] - X)
					final = A[i] + A[s] + A[e]
				e -= 1
		return final


class Solution:

	def closest3Sum(self, nums, N, X):
		nums.sort()
		res = 0
		minn = 999999
		summ = 0
		for i in range(0, len(nums)):
			st = i + 1
			end = len(nums) - 1
			while st < end:
				summ = nums[i] + nums[st] + nums[end]
				if minn >= abs(summ - X):
					res = summ
					minn = abs(X - summ)
				if summ > X:
					end = end - 1
				elif summ <= X:
					st = st + 1
		return res


import math

class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		ans = -1
		dif = math.inf
		for i in range(N - 2):
			a = A[i]
			low = i + 1
			high = N - 1
			while low < high:
				sum = a + A[low] + A[high]
				if abs(sum - X) < dif:
					dif = abs(sum - X)
					ans = sum
				if sum < X:
					low += 1
				else:
					high -= 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		ans = float('INF')
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				diff = sum((A[i], A[j], A[k]))
				if abs(X - diff) < abs(X - ans):
					ans = sum((A[i], A[j], A[k]))
				if diff < X:
					j += 1
				else:
					k -= 1
		return ans


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		res = 0
		dif = 123456789
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				cur = A[i] + A[l] + A[r]
				if dif >= abs(cur - X):
					res = cur
					dif = abs(cur - X)
				if cur > X:
					r -= 1
				elif cur <= X:
					l += 1
		return res


class Solution:

	def closest3Sum(self, A, N, X):
		minimum = 10000000
		A.sort()
		for i in range(len(A) - 2):
			j = i + 1
			k = len(A) - 1
			while j < k:
				res = A[i] + A[j] + A[k] - X
				if abs(res) <= abs(minimum):
					minimum = res
				if res == 0:
					return X
				elif res < 0:
					j += 1
				else:
					k -= 1
		return minimum + X


import sys

class Solution:

	def closest3Sum(self, nums, n, x):
		mini = sys.maxsize
		nums.sort()
		i = 0
		number = -1
		while i < n - 2:
			j = i + 1
			k = n - 1
			while j < k:
				summ = nums[i] + nums[j] + nums[k]
				if abs(x - summ) < mini:
					number = summ
					mini = abs(x - summ)
				if summ - x == 0:
					return summ
				elif summ > x:
					k -= 1
				elif summ < x:
					j += 1
			i += 1
		return number


class Solution:

	def closest3Sum(self, A, N, X):
		maxi = 100000000000
		sum = 0
		A.sort()
		for i in range(N - 2):
			if i == 0 or (i > 0 and A[i] != A[i - 1]):
				low = i + 1
				high = N - 1
				target = -A[i] + X
				while low < high:
					if abs(A[low] + A[high] - target) < maxi:
						sum = A[i] + A[low] + A[high]
						maxi = abs(A[low] + A[high] - target)
					if A[low] + A[high] == target:
						return X
					elif abs(A[low] + A[high]) < target:
						low += 1
					else:
						high -= 1
		return sum


class Solution:

	def closest3Sum(self, A, N, X):
		A.sort()
		ans = 1000000000.0
		res = 0
		for i in range(N - 2):
			if i > 0 and A[i] == A[i - 1]:
				continue
			l = i + 1
			r = N - 1
			while r > l:
				sum = A[l] + A[r] + A[i]
				if ans >= abs(sum - X):
					res = sum
					ans = abs(X - sum)
				if sum > X:
					r -= 1
				elif sum <= X:
					l += 1
		return res


class Solution:

	def closest3Sum(self, a, n, x):
		a.sort()
		ans = 1000000000.0
		res = 0
		for i in range(n - 2):
			if i > 0 and a[i] == a[i - 1]:
				continue
			l = i + 1
			r = n - 1
			while r > l:
				sum = a[l] + a[r] + a[i]
				if ans >= abs(sum - x):
					res = sum
					ans = abs(x - sum)
				if sum > x:
					r -= 1
				elif sum <= x:
					l += 1
		return res


class Solution:

	def closest3Sum(self, num, N, target):
		num.sort()
		result = num[0] + num[1] + num[2]
		for i in range(len(num) - 2):
			(j, k) = (i + 1, len(num) - 1)
			while j < k:
				sum = num[i] + num[j] + num[k]
				if sum == target:
					return sum
				if abs(sum - target) < abs(result - target):
					result = sum
				if sum < target:
					j += 1
				elif sum > target:
					k -= 1
		return result


class Solution:

	def closest3Sum(self, a, n, X):
		diff = 10 ** 6
		ans = 0
		a.sort()
		for i in range(0, n):
			low = i + 1
			high = n - 1
			target = X - a[i]
			while low < high:
				if abs(a[low] + a[high] - target) < diff:
					diff = abs(a[low] + a[high] - target)
					ans = a[low] + a[high] + a[i]
				elif a[low] + a[high] > target:
					high = high - 1
				else:
					low = low + 1
		return ans


class Solution:

	def closest3Sum(self, arr, n, target):
		arr.sort()
		j = 0
		min_diff = -10 ** 5
		while j < n - 2:
			(l, r) = (j + 1, n - 1)
			while l < r:
				sum = arr[l] + arr[r] + arr[j]
				diff = target - sum
				if abs(diff) < abs(min_diff):
					min_diff = diff
				elif diff == 0:
					return target
				elif diff > 0:
					l += 1
				else:
					r += -1
			j += 1
		return target - min_diff


class Solution:

	def closest3Sum(self, arr, n, x):
		arr.sort()
		cl_sum = 1000000000.0
		for i in range(len(arr) - 2):
			pt1 = i + 1
			pt2 = n - 1
			while pt1 < pt2:
				summ = arr[i] + arr[pt1] + arr[pt2]
				if abs(x - summ) < abs(x - cl_sum):
					cl_sum = summ
				if summ > x:
					pt2 -= 1
				else:
					pt1 += 1
		return cl_sum


class Solution:

	def closest3Sum(self, A, N, X):
		closeSum = float('inf')
		A.sort()
		for a in range(N - 2):
			(i, j) = (a + 1, N - 1)
			while i < j:
				sum = A[a] + A[i] + A[j]
				if abs(X - sum) < abs(X - closeSum):
					closeSum = sum
				if sum > X:
					j -= 1
				else:
					i += 1
		return closeSum


class Solution:

	def closest3Sum(self, arr, length, key):
		if length < 3:
			return sum(arr)
		arr.sort()
		min = 99999
		minDiff = 99999
		for i in range(0, length):
			start = i + 1
			end = length - 1
			while start < end:
				sum3 = arr[i] + arr[start] + arr[end]
				diff = abs(sum3 - key)
				if minDiff > diff:
					minDiff = diff
					min = sum3
				if sum3 < key:
					start = start + 1
				elif sum3 > key:
					end = end - 1
				else:
					return sum3
		return min