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
	//loop between start index and last index
		//sum the pair
		temp = arr[i] + arr[j];
		//check for positive sum
			if(temp < positiveClosest)
				positiveClosest = temp;
			//decrement last index
		//check for negative sum
		else if(temp<0)
			if(temp > negativeClosest)
				negativeClosest = temp;
			//increment first index
			printf("The Closest sum is by numbers = %d",(arr[i]+arr[j]));
		printf("%d %d",n1,n2);
		printf("%d %d",p1,p2);	

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

You may also like

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