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