Question

given an array find the numbers whose sum is closest to zero

Answer 1

Find a Pair Whose Sum is Closest to Zero in Array. Problem: This problem is also called minimum absolute sum pair. You are given an array of integers, containing both +ve and -ve numbers. You need to find the two elements such that their sum is closest to zero.

eg. Array [15, 5, -20, 30, -45] O/P should be 15, -20

Solution:

Searching for two numbers (not necessarily consecutive) in an array of positive and negative numbers whose sum is closest to zero? What is the best possible algorithm that comes to your mind?

O(n^2) ?

For each element, find the sum of it with every other element in the array and compare sums. Finally, return the minimum sum. That is simple brute force O(n^2) solution.

Can’t you think up of an O(n lg n) algorithm? Didn’t get hint? Yes, Sorting. See how does sorting will help us.

Steps:

1) Sort all the elements of the array.
2) Keep 2 index variables for left and right index.
3) Initialize: left index l = 0. r = n-1.
4) sum = a[l]+a[r]
5) If sum is negative than l++ else r — .
6) Keep track of absolute min sum.
7) Repeat steps 4,5,6 until l < r