Home Arrays Find two elements in an array such that their sum is closest to 0 (ZERO). (Method 2)

Find two elements in an array such that their sum is closest to 0 (ZERO). (Method 2)

by nikoo28
0 comment

Question: Given an array with both positive and negative numbers, find the two elements such that their sum is closest to zero. ?

Input: arr [] = {1, 60, -10, 70, -80, 85}
Output: -80, 85 (Their sum is -5 that is closest to 0(zero))

What we discussed was the most naive approach by using two for loops. However, this method is not optimized and will take a lot of time if the data is very large. We need to improve the complexity of the program.

One such method is discussed below.

  • Sort all the elements of the given input array.
  • Maintain two indexes one at the beginning (i=0) and one at the end (j=n-1). Also maintain two variables to keep track of smallest positive sum closest to zero and smallest negative sum closest to zero.
  • While (i<j)
    ->If the current pair sum > zero and < positiveClosest, then update the positiveClosest. Decrement j;
    ->If the current pair sum < zero and > negativeClosest, then update the negativeClosest. Increment i.
    ->Else print the pair.

Here is an implementation of the above algorithm.

int twoElementsWithMinSum(int arr[],int size)
{
	//starting index and last index
	int i=0, j=n-1;
	int temp,;
	
	//set the positiveClosest and negativeClosest to
	//maximum and minimum integer values
	int positiveClosest = INT_MAX;
	int negativeClosest = INT_MIN;
	
	//to store the pair of numbers
	int p1=0,p2=0;
	int n1=0,n2=0;
	
	//sort the array
	quickSort(arr,size);
	
	//loop between start index and last index
	while(i<j)
	{
		//sum the pair
		temp = arr[i] + arr[j];
		
		//check for positive sum
		if(temp>0)
		{
			if(temp < positiveClosest)
				positiveClosest = temp;
			
			p1=arr[i];
			p2=arr[j];
			
			//decrement last index
			j--;
		}
		
		//check for negative sum
		else if(temp<0)
		{
			if(temp > negativeClosest)
				negativeClosest = temp;
			
			n1=arr[i];
			n2=arr[j];
			
			//increment first index
			i++;
		}
		else
		{
			printf("The Closest sum is by numbers = %d",(arr[i]+arr[j]));
			return;
		}
	}
	
	if((negativeClosest*-1)<positiveClosest)
		printf("%d %d",n1,n2);
	else
		printf("%d %d",p1,p2);	
}

Time Complexity:- O(n*log(n)), for sorting the array
Space Complexity:- O(1)

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More