Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
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

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





Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



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



© https://www.includehelp.com (2015-2018), Some rights reserved.