Given a sorted array and a number x, find the pair in array whose sum is closest to x

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

Problem :

Given a sorted array,we need to find a pair whose sum is closed to number X in Array.
For example:
array[]={-40,-5,1,3,6,7,8,20};
The pair whose sum is closest to 5 :  1 and 3

Solution : 

Solution 1:

You can check each and every pair of numbers and find the sum close to X.
Java code:
 
  public static void  findPairWithClosestToXBruteForce(int arr[],int X)
  {
   if(arr.length<2)
    return;
   // Suppose 1st two element has minimum diff with X
   int minimumDiff=Math.abs(arr[0]+arr[1]-X);
   int pair1stIndex=0;
   int pair2ndIndex=1;
   for (int i = 0; i < arr.length; i++) {
    for (int j = i+1; j < arr.length; j++) {
     int tempDiff=Math.abs(arr[i]+arr[j]-X);
     
     if(tempDiff< minimumDiff)
     {
      pair1stIndex=i;
      pair2ndIndex=j;
      minimumDiff=tempDiff;
     }
    }
   }
    System.out.println(" The pair whose sum is closest to X using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
  }

 Solution 2: 

  • We will maintain two indexes one at beginning (l=0) and one at end (r=n-1)
  • iterate until l <  r
  • Calculate diff as arr[l] + arr[r]-x
  • if abs (diff) < minDiff then update the minimum sum and pair.
  • If arr[l] + arr[r] is less than X, this means if we want to find sum close to X, do r--
  • If arr[l] + arr[r] is greater than 0,this means if we want to find sum close to X , do l++
Java code:
public static void findPairWithClosestToX(int arr[],int X) {
 
   int minimumDiff = 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 pair for minimumSum
    int minLeft = l, minRight = n-1;
   
    while(l < r)
    {
      
      int currentDiff= Math.abs(arr[l] + arr[r]-X);
      /*If abs(diff) is less than min dif, we need to update sum and pair */
      if(currentDiff < minimumDiff)
      {
        minimumDiff = currentDiff;
        minLeft = l;
        minRight = r;
      }
      if(arr[l] + arr[r] < X)
        l++;
      else
        r--;
    }
   
    System.out.println(" The pair whose sum is closest to X : "+arr[minLeft]+" "+ arr[minRight]);
  }
 }
Time complexity : O(NLogN)

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

package org.arpit.java2blog;

public class FindPairClosestToXMain {

 public static void main(String[] args)
 {
  int array[]={-40,-5,1,3,6,7,8,20};
  findPairWithClosestToXBruteForce(array,5);
  findPairWithClosestToX(array,5);
 }
  public static void  findPairWithClosestToXBruteForce(int arr[],int X)
  {
   if(arr.length<2)
    return;
   // Suppose 1st two element has minimum diff with X
   int minimumDiff=Math.abs(arr[0]+arr[1]-X);
   int pair1stIndex=0;
   int pair2ndIndex=1;
   for (int i = 0; i < arr.length; i++) {
    for (int j = i+1; j < arr.length; j++) {
     int tempDiff=Math.abs(arr[i]+arr[j]-X);
     
     if(tempDiff< minimumDiff)
     {
      pair1stIndex=i;
      pair2ndIndex=j;
      minimumDiff=tempDiff;
     }
    }
   }
    System.out.println(" The pair whose sum is closest to X using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
  }
 
 public static void findPairWithClosestToX(int arr[],int X) {
 
   int minimumDiff = 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 pair for minimumSum
    int minLeft = l, minRight = n-1;
   
    while(l < r)
    {
      
      int currentDiff= Math.abs(arr[l] + arr[r]-X);
      /*If abs(diff) is less than min dif, we need to update sum and pair */
      if(currentDiff < minimumDiff)
      {
        minimumDiff = currentDiff;
        minLeft = l;
        minRight = r;
      }
      if(arr[l] + arr[r] < X)
        l++;
      else
        r--;
    }
   
    System.out.println(" The pair whose sum is closest to X : "+arr[minLeft]+" "+ arr[minRight]);
  }
 }

When you run above program, you will get below output:
   The pair whose sum is closest to X using brute force method: 1 3
The pair whose sum is closest to X : 1 3

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