This post is completed by 1 user

Add to List 
Find two elements whose sum is closest to zero
Objective: Given an array of positive and negative integers, write an algorithm to find the two elements such that their sum is closest to zero.
Example:
int a [] = {1, 4, 5, 3, 2, 10, 6, 20}; Output: Sum close to zero in the given array is : 1 int a [] = {5, 5, 8}; Output: Sum close to zero in the given array is : 0 int a [] = {5, 8}; Output: Sum close to zero in the given array is : 13 int a [] = {5,5,8}; Sum close to zero in the given array is : 10
Approach:
Naive approach: Use 2 loops. For each element in the array, find the sum with every other element and keep track of the minimum sum found.
Time Complexity : O(n^2) Space Complexity: O(1)
Sorting approach:
 Sort the array.
 This will bring all the negative elements to the front and positive elements at the end of the array.
 Track 2 numbers, one positive number close to 0, let’s call it as positiveClose and one negative number close to 0, let’s call it as negativeClose.
 take 2 pointers, one from the beginning of the array and another one from the end of the array. say pointers are i and j.
 Add A[i] + A[j], if sum > 0 then reduce j, j and if sum < 0 then increase i ++.
 If sum > 0 compare it with positiveClose, if positiveClose>sum, do positiveClose = sum.
 If sum < 0 compare it with negativeClose, if negativeClose<sum, do negativeClose = sum.
 Repeat steps 5, 6, 7 till i<j.
 Return the minimum of absolute values of positiveClose and negativeClose, this will be the answer.
 At any point, if sum = 0 then return 0 since this will be the closest to the 0 possible.
 We can easily modify the code given below to track the two indexes as well for which the closest sum is possible.
Time Complexity: O(nlogn) Space Complexity: O(n) by using merge sort.
Code:
Output:
Sum close to zero in the given array is: 1
Also Read: