Find a Pair Whose Sum is Closest to zero in Array

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Problem :

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 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;
   
    // variable 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:

package org.arpit.java2blog;

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

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012