## Wednesday, May 4, 2022

### 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+arr-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+arr-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``````

## You may also like

a
Kubernetes AWS Java Coding Question
Microservices Core Java Python
Spring Framework AI/MLSpring Boot