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)

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)

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