Description: Given an array of size ‘n’ which can contain both positive and negative nos, find 2 elements whose sum is closest to 0.

 
If video does not load, Click here
 
Example:

2  3  -13  -5  6  9

In the above example, the 2 elements are -5 and 6.

Algorithm:

1.        Sort the array using merge-sort.

2.       Intialize variable ‘i’ as the 0(1st element) and ‘j’ as the ‘n-1’(last element).

3.       Intiate variables ‘min_sum’ as INT_MAX, ‘left’ as -1 and ‘right’ as -1. 

4.       Iterate through the array till j > i :

                  -If abs(arr[j]+arr[i])<abs(min_sum)

                  min_sum=arr[i]+arr[j]   ,  left==i   ,   right=j   

                  -If arr[j]+arr[i]<0,

                   i=i+1;

                   Else,

                   j=j-1;

Go to top