# 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
```

What's New

Top Interview Coding Problems/Challenges!

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates