## Wednesday, May 4, 2022

### Question 17 : Find a Pair Whose Sum is Closest to zero in Array

Given array of +ve and -ve integers ,we need to find a pair whose sum is closed to Zero in Array.

For example::
``````array[]={1,3,-5,7,8,20,-40,6};
The pair whose sum is closest to zero :  -5 and 6``````

### Solution :

#### Solution 1:

You can check each and every pair of numbers and find the minimum sum.
Java code:

``public static void findPairWithMinSumBruteForce(int arr[]){    if(arr.length<2)        return;    // Suppose 1st two element has minimum sum    int minimumSum=arr[0]+arr[1];    int pair1stIndex=0;    int pair2ndIndex=1;    for (int i = 0; i < arr.length; i++) {        for (int j = i+1; j < arr.length; j++) {            int tempSum=arr[i]+arr[j];            if(Math.abs(tempSum) < Math.abs(minimumSum))            {                pair1stIndex=i;                pair2ndIndex=j;                minimumSum=tempSum;            }        }    }    System.out.println(" The pair whose sum is closest to zero : "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);}``

#### Solution 2:

• Sort the array.
• We will maintain two indexes one at beginning (l=0) and one at end (r=n-1)
• iterate until l <  r
• Calculate sum of arr[l] + arr[r]
• if abs (sum) < abs (minSum), then update the minimum sum and pair.
• If sum is less than 0, this means if we want to find sum close to 0, do r–
• If sum is greater than 0,this means if we want to find sum close to 0 , do l++
Java code::
``````public static void findPairWithMinSum(int arr[]) {

// Sort the array, you can use any sorting algorithm to sort it
Arrays.sort(arr);
int sum=0;
int minimumSum = Integer.MAX_VALUE;
int n=arr.length;
if(n<0)
return;
// left and right index variables
int l = 0, r = n-1;

// variables to keep track of the left and right index pair for minimumSum
int minLeft = l, minRight = n-1;

while(l < r)
{
sum = arr[l] + arr[r];

/*If abs(sum) is less than min sum, we need to update sum and pair */
if(Math.abs(sum) < Math.abs(minimumSum))
{
minimumSum = sum;
minLeft = l;
minRight = r;
}
if(sum < 0)
l++;
else
r--;
}

System.out.println(" The pair whose sum is minimun : "+arr[minLeft]+" "+ arr[minRight]);
}``````

Time complexity: O(NLogN)

Java program to find a pair whose sum is closest to zero::

``````import java.util.Arrays;

public class findPairClosestToZero {

public static void main(String[] args)
{
int array[]={1,30,-5,70,-8,20,-40,60};
findPairWithMinSumBruteForce(array);
findPairWithMinSum(array);
}
public static void  findPairWithMinSumBruteForce(int arr[])
{
if(arr.length<2)
return;
// Suppose 1st two element has minimum sum
int minimumSum=arr[0]+arr[1];
int pair1stIndex=0;
int pair2ndIndex=1;
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
int tempSum=arr[i]+arr[j];
if(Math.abs(tempSum) < Math.abs(minimumSum))
{
pair1stIndex=i;
pair2ndIndex=j;
minimumSum=tempSum;
}
}
}
System.out.println(" The pair whose sum is closest to zero using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
}

public static void findPairWithMinSum(int arr[]) {

// Sort the array, you can use any sorting algorithm to sort it
Arrays.sort(arr);
int sum=0;
int minimumSum = Integer.MAX_VALUE;
int n=arr.length;
if(n<0)
return;
// left and right index variables
int l = 0, r = n-1;

// variables to keep track of the left and right index pair for minimumSum
int minLeft = l, minRight = n-1;

while(l < r)
{
sum = arr[l] + arr[r];

/*If abs(sum) is less than min sum, we need to update sum and pair */
if(Math.abs(sum) < Math.abs(minimumSum))
{
minimumSum = sum;
minLeft = l;
minRight = r;
}
if(sum < 0)
l++;
else
r--;
}

System.out.println(" The pair whose sum is minimun : "+arr[minLeft]+" "+ arr[minRight]);
}
}``````

When you run the program, you will get the below output::
`````` The pair whose sum is closest to zero using brute force method: 1 -5
The pair whose sum is closest to zero : -5 1
``````

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.