# Two elements whose sum is closest to zero

Question: An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.

For the below array, program should print -80 and 85.

METHOD 1 (Simple)
For each element, find the sum of it with every other element in the array and compare sums. Finally, return the minimum sum.

Implementation:

`# include <stdio.h>`
`# include <stdlib.h> /* for abs() */`
`# include <math.h>`
`void` `minAbsSumPair(``int` `arr[], ``int` `arr_size)`
`{`
`  ``int` `inv_count = 0;`
`  ``int` `l, r, min_sum, sum, min_l, min_r;`
`  ``/* Array should have at least two elements*/`
`  ``if``(arr_size < 2)`
`  ``{`
`    ``printf``(``"Invalid Input"``);`
`    ``return``;`
`  ``}`
`  ``/* Initialization of values */`
`  ``min_l = 0;`
`  ``min_r = 1;`
`  ``min_sum = arr[0] + arr[1];`
`  ``for``(l = 0; l < arr_size - 1; l++)`
`  ``{`
`    ``for``(r = l+1; r < arr_size; r++)`
`    ``{`
`      ``sum = arr[l] + arr[r];`
`      ``if``(``abs``(min_sum) > ``abs``(sum))`
`      ``{`
`        ``min_sum = sum;`
`        ``min_l = l;`
`        ``min_r = r;`
`      ``}`
`    ``}`
`  ``}`
`  ``printf``(``" The two elements whose sum is minimum are %d and %d"``,`
`          ``arr[min_l], arr[min_r]);`
`}`
`/* Driver program to test above function */`
`int` `main()`
`{`
`  ``int` `arr[] = {1, 60, -10, 70, -80, 85};`
`  ``minAbsSumPair(arr, 6);`
`  ``getchar``();`
`  ``return` `0;`
`}`

Output:

```The two elements whose sum is minimum are -80 and 85
```

Time complexity: O(n^2)

METHOD 2 (Use Sorting)
Algorithm
1) Sort all the elements of the input array.
2) Use two index variables l and r to traverse from left and right ends respectively. Initialize l as 0 and r as n-1.
3) sum = a[l] + a[r]
4) If sum is -ve, then l++
5) If sum is +ve, then r–
6) Keep track of abs min sum.
7) Repeat steps 3, 4, 5 and 6 while l < r Implementation

`# include <stdio.h>`
`# include <math.h>`
`# include <limits.h>`
`void` `quickSort(``int` `*, ``int``, ``int``);`
`/* Function to print pair of elements having minimum sum */`
`void` `minAbsSumPair(``int` `arr[], ``int` `n)`
`{`
`  ``// Variables to keep track of current sum and minimum sum`
`  ``int` `sum, min_sum = INT_MAX;`
`  ``// left and right index variables`
`  ``int` `l = 0, r = n-1;`
`  ``// variable to keep track of the left and right pair for min_sum`
`  ``int` `min_l = l, min_r = n-1;`
`  ``/* Array should have at least two elements*/`
`  ``if``(n < 2)`
`  ``{`
`    ``printf``(``"Invalid Input"``);`
`    ``return``;`
`  ``}`
`  ``/* Sort the elements */`
`  ``quickSort(arr, l, r);`
`  ``while``(l < r)`
`  ``{`
`    ``sum = arr[l] + arr[r];`
`    ``/*If abs(sum) is less then update the result items*/`
`    ``if``(``abs``(sum) < ``abs``(min_sum))`
`    ``{`
`      ``min_sum = sum;`
`      ``min_l = l;`
`      ``min_r = r;`
`    ``}`
`    ``if``(sum < 0)`
`      ``l++;`
`    ``else`
`      ``r--;`
`  ``}`
`  ``printf``(``" The two elements whose sum is minimum are %d and %d"``,`
`          ``arr[min_l], arr[min_r]);`
`}`
`/* Driver program to test above function */`
`int` `main()`
`{`
`  ``int` `arr[] = {1, 60, -10, 70, -80, 85};`
`  ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`  ``minAbsSumPair(arr, n);`
`  ``getchar``();`
`  ``return` `0;`
`}`
`/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING`
`    ``PURPOSE */`
`void` `exchange(``int` `*a, ``int` `*b)`
`{`
`  ``int` `temp;`
`  ``temp = *a;`
`  ``*a   = *b;`
`  ``*b   = temp;`
`}`
`int` `partition(``int` `arr[], ``int` `si, ``int` `ei)`
`{`
`  ``int` `x = arr[ei];`
`  ``int` `i = (si - 1);`
`  ``int` `j;`
`  ``for` `(j = si; j <= ei - 1; j++)`
`  ``{`
`    ``if``(arr[j] <= x)`
`    ``{`
`      ``i++;`
`      ``exchange(&arr[i], &arr[j]);`
`    ``}`
`  ``}`
`  ``exchange (&arr[i + 1], &arr[ei]);`
`  ``return` `(i + 1);`
`}`
`/* Implementation of Quick Sort`
`arr[] --> Array to be sorted`
`si  --> Starting index`
`ei  --> Ending index`
`*/`
`void` `quickSort(``int` `arr[], ``int` `si, ``int` `ei)`
`{`
`  ``int` `pi;    ``/* Partitioning index */`
`  ``if``(si < ei)`
`  ``{`
`    ``pi = partition(arr, si, ei);`
`    ``quickSort(arr, si, pi - 1);`
`    ``quickSort(arr, pi + 1, ei);`
`  ``}`
`}`

Output:

```The two elements whose sum is minimum are -80 and 85
```

Time Complexity:
complexity to sort + complexity of finding the optimum pair = O(nlogn) + O(n) = O(nlogn)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/two-elements-whose-sum-is-closest-to-zero/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at