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

Table of Contents [hide]

Problem :
Solution :
- Solution 1:
- Solution 2:
Java program to find a pair 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

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]);
}

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]);
}

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]);
    }
}

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

The pair whose sum is closest to X using brute force method: 1 3

The pair whose sum is closest to X : 1 3

Was this post helpful?

Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.

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

Problem :

Solution :

Solution 1:

Solution 2:

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

Was this post helpful?

Author

Leave a Reply Cancel reply

Categories

Popular Posts

Let’s be Friends

Problem :

Solution :

Solution 1:

Solution 2:

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

Was this post helpful?

Related posts:

Share this

Author

Leave a Reply Cancel reply

Let’s be Friends