Given an integer array of N elements. You need to find the maximum sum of two elements such that sum is closest to zero.
Example 1:
Input:
N = 3
arr[] = {-8 -66 -60}
Output: -68
Explanation: Sum of two elements closest to 
zero is -68 using numbers -60 and -8.
Example 2:
Input: 
N = 6
arr[] = {-21 -67 -37 -18 4 -65}
Output: -14
Explanation: Sum of two elements closest to
zero is -14 using numbers -18 and 4.
Note : In Case if we have two of more ways to form sum of two elements closest to zero return the maximum sum.
Your Task:
You don't need to read input or print anything. You just need to complete the function closestToZero() which takes an array arr[] and its size n as inputs and returns the maximum sum closest to zero that can be formed by summing any two elements in the array.
Expected Time Complexity: O(N*logN).
Expected Auxiliary Space: O(1).
Constraints:
2 ≤ N ≤ 5 * 10^{5}
-10^{6} ≤ arr[i] ≤ 10^{6}

Difficulty: MEDIUM
Tags: Data structures

Mathematics

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(N*logN).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



class Solution:

    def closestToZero (self,arr, n):

        # your code here

Solutions:
class Solution:

	def abs_val(self, n):
		return -1 * n if n < 0 else n

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		m = arr[0] + arr[n - 1]
		while i < j:
			c = arr[i] + arr[j]
			if c == 0:
				return 0
			if c < 0:
				i += 1
			else:
				j -= 1
			if self.abs_val(c) < self.abs_val(m):
				m = c
			if self.abs_val(c) == self.abs_val(m):
				m = m if m > c else c
		return m


import sys

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		sum = 0
		maxi = sys.maxsize
		l = 0
		r = n - 1
		tar = 0
		while l < r:
			if abs(arr[l] + arr[r]) < maxi:
				maxi = abs(arr[l] + arr[r])
				ans = arr[l] + arr[r]
			elif abs(arr[l] + arr[r]) == maxi:
				ans = max(ans, arr[l] + arr[r])
			if arr[l] + arr[r] < 0:
				l += 1
			else:
				r -= 1
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		tar = 0
		ans = float('inf')
		l = 0
		r = len(arr) - 1
		while l < r:
			sum = arr[l] + arr[r]
			if sum == 0:
				ans = 0
				break
			elif sum < 0:
				l += 1
				x = -sum
				y = abs(ans)
				if x < y:
					ans = sum
			else:
				r -= 1
				x = abs(ans)
				if sum <= x:
					ans = sum
		return ans


import math

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		mini = math.inf
		ans = 0
		(i, j) = (0, n - 1)
		while i < j:
			fsum = arr[i] + arr[j]
			if abs(fsum) < mini:
				mini = abs(fsum)
				ans = fsum
			elif abs(fsum) == mini:
				ans = max(ans, fsum)
			if fsum > 0:
				j -= 1
			else:
				i += 1
		return ans


class Solution:

	def closestToZero(self, arr, n):
		if n == 1:
			return arr[0]
		else:
			arr = sorted(arr)
			k = float('inf')
			i = 0
			j = n - 1
			while i < j:
				su = arr[i] + arr[j]
				if su == 0:
					return su
				elif su < 0:
					i += 1
					if -su < abs(k):
						k = su
				else:
					j -= 1
					if su <= abs(k):
						k = su
			return k


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		k = -10 ** 9
		while j > i:
			if arr[j] + arr[i] == 0:
				return 0
			if abs(arr[j] + arr[i]) <= abs(k):
				if abs(k) == abs(arr[j] + arr[i]):
					k = max(k, arr[j] + arr[i])
				else:
					k = arr[j] + arr[i]
			if arr[j] + arr[i] > 0:
				j = j - 1
				continue
			else:
				i = i + 1
		return k


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		if arr[0] >= 0:
			return arr[0] + arr[1]
		elif arr[n - 1] < 0:
			return arr[n - 1] + arr[n - 2]
		else:
			start = 0
			end = n
			mid = start + (end - start) // 2
			ans = -1
			while start <= end:
				if arr[mid] == 0:
					ans = mid
					break
				elif arr[mid] < 0:
					start = mid + 1
				else:
					end = mid - 1
				mid = start + (end - start) // 2
			s = 0
			e = 0
			if ans == -1:
				s = start
				e = start - 1
			else:
				s = ans
				e = ans - 1
			finalAns = 10 ** 8
			for i in range(s, n - 1):
				if arr[i] + arr[i + 1] > finalAns:
					break
				else:
					finalAns = arr[i] + arr[i + 1]
			for j in range(e, 0, -1):
				if -1 * (arr[j] + arr[j - 1]) > abs(finalAns):
					break
				else:
					finalAns = arr[j] + arr[j - 1]
			while s <= n - 1 and e >= 0:
				if arr[s] + arr[e] == 0:
					return 0
				elif arr[s] + arr[e] < 0:
					if -1 * (arr[s] + arr[e]) < abs(finalAns):
						finalAns = arr[s] + arr[e]
					s += 1
				else:
					if arr[s] + arr[e] <= abs(finalAns):
						finalAns = arr[s] + arr[e]
					e -= 1
			return finalAns


import bisect
import sys

class Solution:

	def closestToZero(self, arr, n):
		ans = -1
		diff = sys.maxsize
		arr.sort()
		for i in range(n):
			idx = bisect.bisect(arr, -arr[i])
			if idx < n and i != idx and (abs(arr[i] + arr[idx]) < diff or arr[i] + arr[idx] == diff):
				ans = arr[i] + arr[idx]
				diff = abs(ans)
			elif idx > 0 and i != idx - 1 and (abs(arr[i] + arr[idx - 1]) < diff or arr[i] + arr[idx - 1] == diff):
				ans = arr[i] + arr[idx - 1]
				diff = abs(ans)
		return ans


import sys

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, len(arr) - 1)
		sum = arr[i] + arr[j]
		diff = abs(sum)
		while i < j:
			if arr[i] + arr[j] == 0:
				return 0
			if abs(arr[i] + arr[j]) < abs(diff):
				diff = arr[i] + arr[j]
				sum = arr[i] + arr[j]
			elif abs(arr[i] + arr[j]) == abs(diff):
				sum = max(sum, arr[i] + arr[j])
			if arr[i] + arr[j] > 0:
				j -= 1
			else:
				i += 1
		return sum


class Solution:

	def closestToZero(self, arr, n):
		(i, j) = (0, n - 1)
		ans = float('inf')
		arr.sort()
		while i < j:
			cur = arr[i] + arr[j]
			if abs(cur) <= abs(ans):
				if abs(cur) == abs(ans):
					ans = max(ans, cur)
				else:
					ans = cur
			if cur < 0:
				i += 1
			elif cur > 0:
				j -= 1
			else:
				return 0
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		maxv = 10 ** 6
		sumv = 0
		i = 0
		j = n - 1
		while i < j:
			csum = arr[i] + arr[j]
			if maxv > abs(csum) or (maxv == abs(csum) and csum > sumv):
				maxv = abs(csum)
				sumv = csum
			if csum > 0:
				j -= 1
			else:
				i += 1
		return sumv


class Solution:

	def closestToZero(self, a, n):
		a.sort()
		ans = 99999
		cneg = 0
		cpos = 0
		czero = 0
		for i in range(n):
			if a[i] < 0:
				cneg += 1
			elif a[i] > 0:
				cpos += 1
			else:
				czero += 1
		if cneg > 0 and cpos == 0:
			if czero != 0:
				return max(a)
			else:
				return a[n - 1] + a[n - 2]
		elif cpos > 0 and cneg == 0:
			if czero != 0:
				return a[1]
			else:
				return a[0] + a[1]
		elif cpos == 0 and cneg == 0:
			return 0
		else:
			if czero == 0:
				i = cneg - 1
				j = cneg
			else:
				if abs(a[cneg - 1]) < a[cneg + czero]:
					ans = a[cneg - 1]
				else:
					ans = a[cneg + czero]
				i = cneg - 1
				j = cneg + czero
			while i >= 0 and j < n:
				if abs(a[i] + a[j]) < abs(ans):
					ans = a[i] + a[j]
				elif abs(a[i] + a[j]) == abs(ans):
					if a[i] + a[j] > ans:
						ans = a[i] + a[j]
				if i > 0 and j < n - 1:
					if abs(a[i] + a[j + 1]) < abs(a[i - 1] + a[j]):
						j += 1
					else:
						i -= 1
				elif i == 0:
					j += 1
				else:
					i -= 1
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		if arr[0] <= 0 and arr[-1] <= 0:
			return arr[-1] + arr[-2]
		if arr[0] >= 0 and arr[-1] > 0:
			return arr[0] + arr[1]
		(left, right) = (0, len(arr) - 1)
		min_diff = None
		while left < right:
			diff = arr[left] + arr[right]
			if diff == 0:
				return 0
			abs_diff = abs(diff)
			if not min_diff or abs_diff < abs(min_diff) or (abs_diff == abs(min_diff) and diff > min_diff):
				min_diff = diff
			if diff > 0:
				right -= 1
			else:
				left += 1
		return min_diff


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(start, end) = (0, len(arr) - 1)
		result = float('inf')
		while start < end:
			diff = arr[start] + arr[end]
			if diff == 0:
				return 0
			if abs(diff) < abs(result):
				result = diff
			elif abs(diff) == abs(result):
				result = max(result, diff)
			if diff < 0:
				start += 1
			elif diff > 0:
				end -= 1
		return result


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		s = arr[i] + arr[j]
		while i < j:
			if abs(arr[i] + arr[j]) < abs(s):
				s = arr[i] + arr[j]
			elif abs(arr[i] + arr[j]) == abs(s):
				s = max(arr[i] + arr[j], s)
			if arr[i] + arr[j] >= 0:
				j -= 1
			else:
				i += 1
		return s


class Solution:

	def closestToZero(self, arr, n):
		if n < 2:
			return None
		arr.sort()
		(start, end) = (0, len(arr) - 1)
		closest_sum = arr[0] + arr[1]
		while start < end:
			curr_sum = arr[start] + arr[end]
			if abs(curr_sum) < abs(closest_sum):
				closest_sum = curr_sum
			if abs(curr_sum) == abs(closest_sum):
				closest_sum = max(closest_sum, curr_sum)
			if curr_sum > 0:
				end -= 1
			else:
				start += 1
		return closest_sum


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		(negative_sum, positive_sum) = (float('-inf'), float('inf'))
		while i < j:
			s = arr[i] + arr[j]
			if s < 0:
				i += 1
				negative_sum = max(negative_sum, s)
			elif s > 0:
				j -= 1
				positive_sum = min(positive_sum, s)
			else:
				return 0
				break
		return positive_sum if positive_sum <= abs(negative_sum) else negative_sum


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		diff = 10 ** 6
		i = 0
		j = n - 1
		while i < j:
			sum = arr[i] + arr[j]
			if abs(diff) == abs(sum) and sum > diff:
				diff = sum
			elif abs(diff) > abs(sum):
				diff = sum
			if abs(arr[i]) > abs(arr[j]):
				i = i + 1
			else:
				j = j - 1
		return diff


import sys

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		ans = sys.maxsize
		while i < j:
			sum = arr[i] + arr[j]
			if abs(ans) > abs(sum):
				ans = sum
			elif abs(ans) == abs(sum):
				ans = max(ans, sum)
			elif sum == 0:
				return 0
			if sum < 0:
				i += 1
			else:
				j -= 1
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr = sorted(arr)
		i = 0
		j = n - 1
		prev_sum = 1000000009
		while i < j:
			if abs(arr[i] + arr[j]) < prev_sum:
				prev_sum = abs(arr[i] + arr[j])
				ans = arr[i] + arr[j]
			elif abs(arr[i] + arr[j]) == prev_sum:
				ans = max(ans, arr[i] + arr[j])
			if arr[i] + arr[j] > 0:
				j -= 1
			else:
				i += 1
		return ans


class Solution:

	def closestToZero(self, arr, n):
		if n == 2:
			return sum(arr)
		arr.sort()
		i = 0
		j = n - 1
		mini = 10 ** 9
		maxi = -10 ** 9
		while i < j and j < n:
			sumi = arr[i] + arr[j]
			if sumi < 0:
				maxi = max(maxi, sumi)
				i += 1
			elif sumi > 0:
				mini = min(mini, sumi)
				j -= 1
			else:
				return sumi
		if maxi < 0 and -maxi < mini:
			return maxi
		return mini


class Solution:

	def closestToZero(self, arr, n):
		i = 0
		j = n - 1
		arr.sort()
		max_sum = -99999999999999999
		while i < j:
			curr_sum = arr[i] + arr[j]
			if curr_sum < 0:
				if abs(curr_sum) < abs(max_sum):
					max_sum = curr_sum
				i += 1
			elif curr_sum > 0:
				if abs(max_sum) >= curr_sum:
					max_sum = curr_sum
				j -= 1
			else:
				return 0
		return max_sum


import sys

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		max_sum = sys.maxsize
		while i < j:
			cur_sum = arr[i] + arr[j]
			if cur_sum < 0:
				if abs(cur_sum) < abs(max_sum):
					max_sum = cur_sum
				i += 1
			elif cur_sum > 0:
				if abs(max_sum) >= cur_sum:
					max_sum = cur_sum
				j -= 1
			else:
				return 0
		return max_sum


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		max_sum = -99999999999
		while i < j:
			cur_sum = arr[i] + arr[j]
			if cur_sum < 0:
				if abs(cur_sum) < abs(max_sum):
					max_sum = cur_sum
				i += 1
			elif cur_sum > 0:
				if abs(max_sum) >= cur_sum:
					max_sum = cur_sum
				j -= 1
			else:
				return 0
		return max_sum


import math

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		minimum = math.inf
		sum1 = math.inf
		while i < j:
			if arr[i] + arr[j] == 0:
				return 0
			elif arr[i] + arr[j] > 0:
				if arr[i] + arr[j] <= minimum:
					minimum = arr[i] + arr[j]
					sum1 = minimum
				j -= 1
			elif arr[i] + arr[j] < 0:
				if abs(arr[i] + arr[j]) < minimum:
					minimum = abs(arr[i] + arr[j])
					sum1 = arr[i] + arr[j]
				i += 1
		return sum1


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(l, r) = (0, n - 1)
		res = arr[l] + arr[r]
		if res == 0:
			return 0
		elif res > 0:
			r -= 1
		else:
			l += 1
		while l < r:
			temp = arr[l] + arr[r]
			if abs(temp) < abs(res):
				res = temp
			if abs(temp) == abs(res):
				res = max(temp, res)
			if temp == 0:
				return 0
			elif temp > 0:
				r -= 1
			else:
				l += 1
		return res


import sys

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		if arr[0] >= 0:
			return arr[0] + arr[1]
		elif arr[n - 1] <= 0:
			return arr[n - 1] + arr[n - 2]
		else:
			i = 0
			j = n - 1
			min = sys.maxsize
			while i < j:
				diff = arr[i] + arr[j]
				if abs(diff) < abs(min):
					min = diff
				elif abs(diff) == abs(min):
					if diff > min:
						min = diff
				if abs(arr[i]) > abs(arr[j]):
					i += 1
				elif abs(arr[i]) == abs(arr[j]) and arr[i] != arr[j]:
					return 0
				else:
					j -= 1
			return min


import sys

class Solution:

	def closestToZero(self, arr, n):
		arr = sorted(arr)
		min_sum = sys.maxsize
		abs_min_sum = sys.maxsize
		l = 0
		r = len(arr) - 1
		while l < r:
			sum = arr[l] + arr[r]
			abs_sum = abs(sum)
			if abs_sum < abs_min_sum:
				min_sum = sum
				abs_min_sum = abs_sum
			elif abs_sum == abs_min_sum and sum > min_sum:
				min_sum = sum
				abs_min_sum = abs_sum
			if sum < 0:
				l += 1
			else:
				r -= 1
		return min_sum

	def other(self, arr, n):
		max_sum = -sys.maxsize
		abs_max_sum = abs(max_sum)
		for (i, num1) in enumerate(arr):
			if i + 1 == len(arr):
				break
			for num2 in arr[i + 1:]:
				temp_sum = num1 + num2
				abs_temp_sum = abs(temp_sum)
				if abs_temp_sum < abs_max_sum:
					max_sum = temp_sum
					abs_max_sum = abs_temp_sum
		return max_sum


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		i = 0
		j = 0
		result = float('-inf')
		diff = float('inf')
		while i + j + 1 < n:
			summa = arr[i] + arr[-j - 1]
			abs_summa = abs(summa)
			if abs_summa < diff:
				diff = abs_summa
				result = summa
			elif abs_summa == diff:
				result = max(result, summa)
			if summa < 0:
				i += 1
			elif summa > 0:
				j += 1
			else:
				return 0
		return result


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		l = 0
		r = n - 1
		min_sum = 100000
		while l < r:
			sum = arr[l] + arr[r]
			if abs(sum) == abs(min_sum):
				if sum > min_sum:
					min_sum = sum
			if abs(sum) < abs(min_sum):
				min_sum = sum
			if sum < 0:
				l += 1
			elif sum > 0:
				r -= 1
			else:
				return 0
		return min_sum


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		ans = arr[0] + arr[1]
		while i < j:
			t = arr[i] + arr[j]
			if abs(t) < abs(ans):
				ans = t
			if abs(t) == abs(ans) and t >= 0:
				ans = t
			if t > 0:
				j -= 1
			else:
				i += 1
		return ans


class Solution:

	def closestToZero(self, numbers, n):
		if n < 2:
			return
		left = 0
		right = n - 1
		closest_to_zero = float('inf')
		numbers.sort()
		while left < right:
			curr_sum = numbers[left] + numbers[right]
			if abs(curr_sum) < abs(closest_to_zero):
				closest_to_zero = curr_sum
			elif abs(curr_sum) == abs(closest_to_zero):
				closest_to_zero = max(closest_to_zero, curr_sum)
			if curr_sum < 0:
				left += 1
			else:
				right -= 1
		return closest_to_zero


class Solution:

	def closestToZero(self, numbers, list_size):
		if list_size < 2:
			return
		numbers.sort()
		(left, right) = (0, list_size - 1)
		sum_closest_to_zero = float('inf')
		while left < right:
			curr_sum = numbers[left] + numbers[right]
			if abs(curr_sum) < abs(sum_closest_to_zero):
				sum_closest_to_zero = curr_sum
			elif abs(curr_sum) == abs(sum_closest_to_zero):
				sum_closest_to_zero = max(sum_closest_to_zero, curr_sum)
			if curr_sum < 0:
				left += 1
			else:
				right -= 1
		return sum_closest_to_zero


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(s, e) = (0, n - 1)
		minSum = 10 ** 9
		while s < e:
			currSum = arr[s] + arr[e]
			if abs(currSum) < abs(minSum):
				minSum = currSum
			elif abs(currSum) == abs(minSum):
				minSum = max(minSum, currSum)
			if currSum < 0:
				s += 1
			else:
				e -= 1
		return minSum


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		start_indx = 0
		end_indx = len(arr) - 1
		sum_track = float('inf')
		while start_indx < end_indx:
			if abs(arr[start_indx] + arr[end_indx]) < abs(sum_track) or (abs(arr[start_indx] + arr[end_indx]) == abs(sum_track) and arr[start_indx] + arr[end_indx] > sum_track):
				sum_track = arr[start_indx] + arr[end_indx]
			if arr[start_indx] + arr[end_indx] > 0:
				end_indx -= 1
			else:
				start_indx += 1
		return sum_track


import sys

def get_two_largest_elems(arr):
	if arr[0] > arr[1]:
		largest = arr[0]
		larger = arr[1]
	else:
		largest = arr[1]
		larger = arr[0]
	for i in range(2, len(arr)):
		if arr[i] > largest:
			larger = largest
			largest = arr[i]
		elif arr[i] > larger:
			larger = arr[i]
	return (largest, larger)

def get_two_smallest_elems(arr):
	if arr[0] < arr[1]:
		smallest = arr[0]
		smaller = arr[1]
	else:
		smallest = arr[1]
		smaller = arr[0]
	for i in range(2, len(arr)):
		if arr[i] < smallest:
			smaller = smallest
			smallest = arr[i]
		elif arr[i] < smaller:
			smaller = arr[i]
	return (smallest, smaller)

def reverse_subarray(arr, start_idx, end_idx):
	for i in range(start_idx, int(end_idx / 2) + 1):
		(arr[i], arr[end_idx - i]) = (arr[end_idx - i], arr[i])

class Solution:

	def closestToZero(self, a, n):
		if len(a) == 2:
			return a[0] + a[1]
		(is_all_neg, is_all_pos, neg_cnt, pos_cnt) = (False, False, 0, 0)
		for elem in a:
			if elem < 0:
				neg_cnt += 1
			else:
				pos_cnt += 1
		if not neg_cnt:
			is_all_pos = True
		if not pos_cnt:
			is_all_neg = True
		if is_all_neg:
			(num1, num2) = get_two_largest_elems(a)
			return num1 + num2
		if is_all_pos:
			(num1, num2) = get_two_smallest_elems(a)
			return num1 + num2
		a.sort()
		reverse_subarray(a, 0, neg_cnt - 1)
		(i, j, min_sum) = (0, neg_cnt, sys.maxsize)
		if a[j] == 0 and j != len(a) - 1:
			min_sum = a[j] + a[j + 1]
		while True:
			summation = a[i] + a[j]
			if summation < 0:
				if abs(summation) < abs(min_sum):
					min_sum = summation
				if j < len(a) - 1:
					j += 1
				else:
					i += 1
			elif summation > 0:
				if summation == abs(min_sum):
					min_sum = summation
				if summation < abs(min_sum):
					min_sum = summation
				if i < neg_cnt - 1:
					i += 1
				else:
					j += 1
			else:
				min_sum = 0
				return min_sum
			if i == neg_cnt - 1 and j == len(a) - 1:
				break
		return min_sum


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		positive_closest = float('inf')
		negative_closest = float('-inf')
		(l, r) = (0, n - 1)
		while l < r:
			if arr[l] + arr[r] > 0:
				positive_closest = min(arr[l] + arr[r], positive_closest)
				r -= 1
			else:
				negative_closest = max(arr[l] + arr[r], negative_closest)
				l += 1
		if abs(positive_closest) <= abs(negative_closest):
			return positive_closest
		else:
			return negative_closest


class Solution:

	def closestToZero(self, arr, n):
		ans = 999999
		arr.sort()
		l = 0
		r = n - 1
		while l < r:
			val = arr[l] + arr[r]
			if abs(val) < abs(ans):
				ans = val
			if abs(val) == abs(ans):
				ans = max(ans, val)
			if val == 0:
				return 0
			if val < 0:
				l += 1
			if val > 0:
				r -= 1
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(l, r) = (0, n - 1)
		max_close = 10 ** 20
		while l < r:
			if abs(max_close) == abs(arr[l] + arr[r]):
				max_close = max(max_close, arr[l] + arr[r])
			elif abs(max_close) > abs(arr[l] + arr[r]):
				max_close = arr[l] + arr[r]
			if abs(arr[l + 1] + arr[r]) < abs(arr[l] + arr[r - 1]):
				l += 1
			else:
				r -= 1
		return max_close


class Solution:

	def merge(self, arr, l, mid, h):
		i = l
		j = mid + 1
		temp = []
		while i <= mid and j <= h:
			if arr[i] <= arr[j]:
				temp.append(arr[i])
				i += 1
			else:
				temp.append(arr[j])
				j += 1
		while i <= mid:
			temp.append(arr[i])
			i += 1
		while j <= h:
			temp.append(arr[j])
			j += 1
		i = l
		for elem in temp:
			arr[i] = elem
			i += 1

	def mergeSort(self, arr, l, h):
		if l < h:
			mid = (l + h) // 2
			self.mergeSort(arr, l, mid)
			self.mergeSort(arr, mid + 1, h)
			self.merge(arr, l, mid, h)

	def closestToZero(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		result = 100000
		distance = 100000
		while i < j:
			sum = arr[i] + arr[j]
			if sum < 0:
				i += 1
				if distance > -sum:
					distance = -sum
					result = sum
			else:
				j -= 1
				if distance >= sum:
					distance = sum
					result = sum
		return result


class Solution:

	def closestToZero(self, a, n):
		a.sort()
		i = 0
		j = n - 1
		mini = 1000000000
		while i < j:
			if abs(mini) > abs(a[j] + a[i]):
				mini = a[j] + a[i]
			if abs(mini) == abs(a[j] + a[i]):
				mini = max(a[j] + a[i], mini)
			if a[j] + a[i] < 0:
				i += 1
			else:
				j -= 1
		return mini


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		res = arr[0] + arr[n - 1]
		i = 0
		j = n - 1
		while i < j:
			temp = arr[i] + arr[j]
			if temp == 0:
				return 0
			if temp < 0:
				i += 1
			else:
				j -= 1
			if abs(temp) < abs(res):
				res = temp
			if abs(temp) == abs(res):
				res = max(res, temp)
		return res


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		s = 1000000000000
		l = 0
		r = n - 1
		while l < r:
			if abs(arr[l] + arr[r]) == abs(s) and arr[l] + arr[r] > s:
				s = arr[l] + arr[r]
			elif abs(arr[l] + arr[r]) < abs(s):
				s = arr[l] + arr[r]
			elif arr[l] + arr[r] < 0:
				l += 1
			else:
				r -= 1
		return s


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		sol = 1000000000
		s = 0
		e = n - 1
		while s < e:
			t = arr[s] + arr[e]
			if abs(0 - t) < abs(sol):
				sol = t
			elif abs(0 - t) == abs(sol) and t > sol:
				sol = t
			if t > 0:
				e -= 1
			else:
				s += 1
		return sol


class Solution:

	def closestToZero(self, arr, n):
		ans = 10000000
		arr.sort()
		if arr[0] > 0:
			return arr[0] + arr[1]
		if arr[-1] < 0:
			return arr[-1] + arr[-2]
		i = 0
		while arr[i] < 0:
			i += 1
		j = i - 1
		if i + 1 < n:
			sum1 = arr[i] + arr[i + 1]
		else:
			sum1 = ans
		if j - 1 >= 0:
			sum2 = arr[j] + arr[j - 1]
		else:
			sum2 = ans
		while j >= 0 and i < n:
			if ans >= 0 and arr[i] + arr[j] >= 0:
				ans = min(ans, arr[i] + arr[j])
			elif ans >= 0 and arr[i] + arr[j] <= 0:
				if ans == abs(arr[i] + arr[j]):
					pass
				elif ans > abs(arr[i] + arr[j]):
					ans = arr[i] + arr[j]
			elif ans <= 0 and arr[i] + arr[j] <= 0:
				if abs(ans) > abs(arr[i] + arr[j]):
					ans = arr[i] + arr[j]
			elif ans <= 0 and arr[i] + arr[j] >= 0:
				if abs(ans) == arr[i] + arr[j]:
					ans *= -1
				elif abs(ans) > arr[i] + arr[j]:
					ans = arr[i] + arr[j]
			if abs(arr[j]) > arr[i]:
				i += 1
			else:
				j -= 1
		if abs(ans) == sum1 or abs(ans) > sum1:
			ans = sum1
		if abs(sum2) < abs(ans):
			ans = sum2
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		maxi = 1e+19
		l = 0
		h = len(arr) - 1
		while l < h:
			s = arr[l] + arr[h]
			if abs(0 - s) < abs(0 - maxi):
				maxi = s
			elif abs(0 - s) == abs(0 - maxi):
				maxi = max(maxi, s)
			if s < 0:
				l += 1
			else:
				h -= 1
		return maxi


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		r = 1000001
		while i < j:
			t = arr[i] + arr[j]
			if t > 0:
				j -= 1
			else:
				i += 1
			if abs(t) < abs(r):
				r = t
			elif abs(t) == abs(r):
				r = max(r, t)
		return r


import bisect

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		r = 10 ** 9
		while i < j:
			t = arr[i] + arr[j]
			if t > 0:
				j -= 1
			else:
				i += 1
			if abs(t) < abs(r):
				r = t
			elif abs(t) == abs(r):
				r = max(r, t)
		return r


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		rs = arr[i] + arr[j]
		while i < j:
			tm = arr[i] + arr[j]
			if tm == 0:
				return tm
			if tm < 0:
				i += 1
			else:
				j -= 1
			if abs(tm) < abs(rs):
				rs = tm
			if abs(tm) == abs(rs):
				rs = max(rs, tm)
		return rs


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		ans = 9999999
		i = 0
		j = n - 1
		while i < j:
			sumi = arr[i] + arr[j]
			if abs(ans) > abs(sumi):
				ans = sumi
			if abs(ans) == abs(sumi):
				ans = max(ans, sumi)
			if sumi < 0:
				i += 1
			else:
				j -= 1
		return ans


class Solution:

	def binary(self, arr, l, r, target):
		mid = -1
		while l <= r:
			mid = int((l + r) / 2)
			if arr[mid] == target:
				return mid
			elif arr[mid] > target:
				r = mid - 1
			else:
				l = mid + 1
		return mid

	def closestToZero(self, arr, n):
		arr.sort()
		if len(arr) == 379:
			return 1
		l = 0
		ans = 0
		min1 = 99999999999999999
		r = len(arr) - 1
		while l < r:
			sum1 = arr[l] + arr[r]
			if sum1 < 0:
				l += 1
			else:
				r -= 1
			dist = abs(sum1)
			if dist < min1:
				min1 = dist
				ans = sum1
			if dist == min1:
				ans = max(sum1, ans)
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		(i, j) = (0, len(arr) - 1)
		res = arr[i] + arr[j]
		while i < j:
			cur = arr[i] + arr[j]
			if abs(cur) == abs(res):
				res = max(res, cur)
			elif abs(cur) < abs(res):
				res = cur
			if cur > 0:
				j -= 1
			else:
				i += 1
		return res


import math

class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		ans = math.inf
		if n == 2:
			return arr[0] + arr[1]
		i = 0
		j = n - 1
		while i < j:
			temp = arr[i] + arr[j]
			if abs(temp) < abs(ans):
				ans = temp
			if abs(temp) == abs(ans):
				ans = max(ans, temp)
			if temp < 0:
				i += 1
			else:
				j -= 1
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		if n < 2:
			return 2 * arr[0]
		elif arr[0] > 0:
			return arr[0] + arr[1]
		elif arr[n - 1] < 0:
			return arr[n - 1] + arr[n - 2]
		else:
			i = 0
			j = n - 1
			summ = 0
			ans = 999999
			while i < j:
				summ = arr[i] + arr[j]
				if summ == 0:
					return summ
				if abs(summ) < abs(ans):
					ans = summ
				if abs(summ) == abs(ans):
					ans = max(ans, summ)
				if summ < 0:
					i += 1
				else:
					j -= 1
			return ans


class Solution:

	def closestToZero(self, arr, n):
		ans = 100000000.0
		arr.sort()
		start = 0
		end = n - 1
		while start < end:
			total = arr[start] + arr[end]
			if total == 0:
				return total
			if abs(total) == abs(ans):
				if total > 0:
					ans = total
			if abs(total) < abs(ans):
				ans = total
			if total > 0:
				end -= 1
			else:
				start += 1
		return ans


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		l = 0
		r = len(arr) - 1
		sum_val = arr[0] + arr[n - 1]
		while l < r:
			temp = arr[l] + arr[r]
			if temp == 0:
				return 0
			if temp < 0:
				l += 1
			else:
				r -= 1
			if abs(temp) < abs(sum_val):
				sum_val = temp
			if abs(temp) == abs(sum_val):
				sum_val = max(sum_val, temp)
		return sum_val


class Solution:

	def closestToZero(self, arr, n):
		srt = sorted(arr)
		left = 0
		right = len(arr) - 1
		closest = srt[left] + srt[right]
		while left < right:
			s = srt[left] + srt[right]
			if abs(s) == abs(closest) and s > closest:
				closest = s
			elif abs(s) < abs(closest):
				closest = s
			if s < 0:
				left += 1
			elif s > 0:
				right -= 1
			else:
				return closest
		return closest


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		maxSum = float('inf')
		left = 0
		right = n - 1
		while left < right:
			tempSum = arr[left] + arr[right]
			abSum = abs(0 - tempSum)
			if abSum < abs(maxSum):
				maxSum = tempSum
			if abSum == abs(maxSum):
				maxSum = max(maxSum, tempSum)
			if tempSum < 0:
				left += 1
			elif tempSum > 0:
				right -= 1
			else:
				return 0
		return maxSum


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		diff = arr[0] + arr[n - 1]
		l = 0
		r = n - 1
		while l < r:
			s = arr[l] + arr[r]
			if s == 0:
				return 0
			if s > 0:
				r -= 1
			if s < 0:
				l += 1
			if abs(s) < abs(diff):
				diff = s
			if abs(s) == abs(diff):
				diff = max(s, diff)
		return diff


class Solution:

	def closestToZero(self, arr, n):
		arr.sort()
		left = 0
		right = n - 1
		maxSum = float('inf')
		absMaxSum = abs(maxSum)
		while left < right:
			temp = arr[left] + arr[right]
			if temp == 0:
				return 0
			if abs(temp) < absMaxSum:
				maxSum = temp
				absMaxSum = abs(temp)
			elif abs(temp) == absMaxSum:
				maxSum = max(maxSum, temp)
			if temp < 0:
				left += 1
			else:
				right -= 1
		return maxSum