**Objective: **Given an array of positive and negative integers, write a algorithm to find the two elements such their sum is closest to zero.

**Example:**

inta [] = {1, 4, -5, 3, -2, 10, -6, 20};Output: Sum close to zero in the given array is : 1inta [] = {-5, 5, 8};Output: Sum close to zero in the given array is : 0inta [] = {5, 8};Output: Sum close to zero in the given array is : 13inta [] = {-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 at 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 the step 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 is 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.

**Complete Code:**

import java.util.*; | |

public class SumCloseToZero { | |

public int findSum(int [] a){ | |

Arrays.sort(a); | |

int i=0; | |

int j = a.length–1; | |

int positiveClose = Integer.MAX_VALUE; | |

int negativeClose = Integer.MIN_VALUE; | |

while(i<j){ | |

int temp = a[i] + a[j]; | |

//check if temp is greater than 0 | |

if(temp>0){ | |

//check if positiveClose needs to be updated | |

if(positiveClose>temp){ | |

positiveClose = temp; | |

} | |

//decrement j, in order to reduce the difference, close to 0 | |

j—; | |

}else if(temp<0){ | |

//check if negative needs to be updated | |

if(negativeClose<temp){ | |

negativeClose = temp; | |

} | |

//increment i, in order to reduce the difference, close to 0 | |

i++; | |

}else{ | |

//means temp is 0, that is the closest to zero we can get, return 0 | |

return 0; | |

} | |

} | |

//check the least absolute value in postiveClose and negativeClose | |

return Math.min(Math.abs(positiveClose), Math.abs(negativeClose)); | |

} | |

public static void main(String[] args) { | |

int a [] = {1, 4, –5, 3, –2, 10, –6, 20}; | |

int closestSum = new SumCloseToZero().findSum(a); | |

System.out.println("Sum close to zero in the given array is : " + closestSum); | |

} | |

} | |

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