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

Given a sorted array, we need to find a pair whose sum is closed to the number X in the Array.

For example::

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

Solution :

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

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 the above program, you will get the 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

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

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest