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

I guess now its easy to implement.

Implementation:
Sorting function (Quick Sort already explained in our previous posts. Quick Sort)

/* Function to print pair of elements having minimum sum */
void minAbsSumPair(int arr[], int n)
{
	int l, r , min_sum, sum = 0, min_l, min_r;

	/* Array should have at least two elements*/
	if(n < 2)
	{
		printf("Invalid Input");
		return;
	} 

	/* Sort the elements */
	quickSort(arr, 0, n-1);


	/* Start looking for the pair  */
	l = 0; r = n-1;
	min_sum = arr[l] + arr[r];
	min_l = l; 
	min_r = 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]);
}

/* Main program to test above function */
int main()
{
	int arr[] = {15, 5, -20, 30, -45};
	minAbsSumPair(arr, 5);
	getchar();
	return 0;
}

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

3 Thoughts on “Find a Pair Whose Sum is Closest to Zero in Array

  1. Aakash Wankhede on September 30, 2014 at 10:31 pm said:

    Venkatesh Kotrike ::This is will give u a answer for array {-45, -20, -2, -1, 12, 15, 30}

    package javaapplication8;

    import static java.lang.Math.abs;

    class abc
    {
    void minAbsSumPair(int arr[], int n)

    {

    int l, r , min_sum, sum = 0, min_l, min_r;

    /* Array should have at least two elements*/

    if(n < 2)

    {

    System.out.println("Invalid Input");

    return;

    }

    /* Sort the elements */
    /* Start looking for the pair */

    l = 0; r = n-1;

    min_sum = arr[l] + arr[r];

    min_l = l;

    min_r = 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–;
    }
    System.out.println(" The two elements whose sum is minimum are" +arr[min_l]+ "and" +arr[min_r]);
    }
    }

    public class JavaApplication8
    {
    public static void main(String[] args)
    {
    abc a =new abc();
    int arr[] = {-45, -20, -2, -1, 12, 15, 30};

    a.minAbsSumPair(arr, 7);
    }
    }

  2. Vishwakarma on October 22, 2014 at 12:11 pm said:

    private static void findTwoNumWithSumZero(int[] a) {
    List list=new ArrayList();
    HashMap hm=new HashMap();
    for(int i=0;i<a.length;i++){
    int sum=0;
    for(int j=i+1;j<a.length;j++){
    sum=a[i]+a[j];
    list.add(Math.abs(sum));
    hm.put(Math.abs(sum), i+";"+j);
    }
    }
    Collections.sort(list);
    String b[]=hm.get(list.get(0)).split(";");
    System.out.println(a[Integer.parseInt(b[0])]);
    System.out.println(a[Integer.parseInt(b[1])]);
    }

  3. Tejas Kasalkar on October 22, 2014 at 7:03 am said:

    public class MinAbsSum {

    public static void main(String[] args) {
    int a[]={-45, -20, -2, -1, 12, 15, 30 };

    // Let the first two numbers of array be required paired
    int p1=a[0],p2=a[1],msum=a[0]+a[1];

    /* if sum is negative then make it positive.
    Logic is if i convert all "sums" to positive then the smallest
    sum would be the one closest to zero*/

    if(msum<0)
    msum=msum*-1;

    int tsum;// temporary sum variable
    for(int i=0;i<a.length;i++)
    {
    for(int j=i+1;j<a.length;j++)
    {
    tsum=a[i]+a[j]; // adding two elements and storing it in tsum

    if(tsum<0)
    tsum=tsum*-1;//if sum is negative then make it positive.

    //If current sum of elements is less than minimum sum then
    // those are the required elements or pair
    if(tsum<msum)
    { p1=a[i]; p2=a[j]; msum=tsum;}
    }
    }

    System.out.println("Two elements whose sum is closest to zero are :"+p1+" "+p2);
    }

    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation