# Find two elements whose sum is closest to zero

Objec­tive: Given an array of pos­i­tive and neg­a­tive inte­gers, write a algo­rithm to find the two ele­ments such their sum is clos­est to zero.

Exam­ple:

```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 ele­ment in the array, find the sum with every other ele­ment and keep track of the min­i­mum sum found.

Time Com­plex­ity : O(n^2) Space Com­plex­ity: O(1)

Sort­ing approach:

1. Sort the array.
2. This will bring all the neg­a­tive ele­ments at the front and pos­i­tive ele­ments at the end of the array.
3. Track 2 num­bers, one pos­i­tive num­ber close to 0, let’s call it as pos­i­tive­Close  and one neg­a­tive num­ber close to 0, let’s call it as negativeClose.
4. take 2 point­ers, one from the begin­ning of the array and another one from the end of the array. say point­ers are i and j.
5. Add A[i] + A[j], if sum > 0 then reduce j, j– and if sum < 0 then increase i ++.
6. If sum > 0 com­pare it with pos­i­tive­Close, if positiveClose>sum, do pos­i­tive­Close = sum.
7. If sum < 0 com­pare it with neg­a­tive­Close, if negativeClose<sum, do neg­a­tive­Close = sum.
8. Repeat the step 5, 6, 7 till i<j.
9. Return the min­i­mum of absolute val­ues of pos­i­tive­Close and neg­a­tive­Close, this will be the answer.
10. At any point if sum = 0 then return 0 since this will be the clos­est to the 0 is possible.
11. We can eas­ily mod­ify the code given below to track the two indexes as well for which the clos­est sum is possible.

Time Com­plex­ity : O(nlogn) Space Com­plex­ity: O(n) by using merge sort.

Com­plete Code:

```Output:
Sum close to zero in the given array is : 1
```

#### You may also like...

• lipsa patel

The solu­tion does not return neg­a­tive clos­est sum.

Arrays.sort(array);

int i = 0;
int j = array.length — 1;

int left­In­dex = 0;
int rightIn­dex = array.length — 1;

int min­i­mum­Sum = Integer.MAX_VALUE;
int sum;

if (array.length < 2) { //For one ele­ment return that ele­ment
return array[0];
}

while(i < j) {

sum = array[i] + array[j];

if (Math.abs(sum) < Math.abs(minimumSum)) {
min­i­mum­Sum = sum;
left­In­dex = i;
rightIn­dex = j;
}

if (sum < 0) {
i++;
} else {
j–;
}
}

System.out.println(“The two ele­ments whose sum is mim­i­mum is ” + array[leftIndex] + “, ” + array[rightIndex]);
return minimumSum;