Home » Algorithms

Find the pair whose sum is closest to zero in minimum time complexity

Given an array with both positive and negative integers. Find the pair whose sum is closest to zero in minimum time complexity.
Submitted by Radib Kar, on November 06, 2018

Problem statement

Given an array with both positive and negative integers. Find the pair whose sum is closest to zero in minimum time complexity.

Description:

Here we are going to see the algorithm with minimum time complexity to find a pair such that their sum is closest to 0.

Algorithm

1. Sort the array.
2. Maintain two indexes, one at beginning, i, (i=0) & the other at the ending, j, (j=n-1, where n is the array length).
3. Maintain two variables indexP and indexN to keep track of the pairs which sum closest to 0.
4. Set a variable minsum to INT_MAX.
5. While (i<j)
   • If abs(current pair-sum)< abs(minsum)
     Then
     minsum=current pair-sum.
     indexP=j;
     indexN=i;
   • If(current pair-sum>0)
     Decrement j;
     Else
     Increment i;
6. End loop
7. indexP & indexN marks to the pair that sum closest to 0.
8. Print array[indexN] & array[indexP].

Time complexity: O(nlogn) (O(logn) for sorting the array)

Space complexity: O(1)

C++ implementation of the algorithm

#include<bits/stdc++.h>
using namespace std;

void findpairs(int* a, int n){
	//sort the array using default sort library function, O(logn) generally
	sort(a,a+n);   
	int temp,i=0,j=n-1,minsum=INT_MAX,indexN=i,indexP=j;

	while(i<j){
		// current pair-sum
		temp=a[i]+a[j];  
		//if abs(current pair-sum)<abs(minsum)
		if(abs(temp)<abs(minsum)){      
			minsum=temp;
			indexN=i;
			indexP=j;
		}
		//if current pair-sum<0
		if(temp<0){  
			//Increment i
			i++;           
		}
		else		
		j--; // Decrement j
	}
	
	//print the pair
	cout<<"the pair is "<<a[indexN]<<","<<a[indexP]<<endl;    
}

int main(){

	int x,count=0,n;

	// enter array length
	cout<<"enter no of elements\n";        
	cin>>n;
	
	int* a=(int*)(malloc(sizeof(int)*n));
	
	//fill the array
	cout<<"enter elements................\n";  
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);

	findpairs(a,n);           

	return 0;	
}

Output

enter no of elements
9
enter elements................
11
-4
7 
31
-30
-6
8
17
-14
the pair is -30,31