# Find the pair of elements in the sorted array whose sum is closest to a given number X

0
731

## Given a sorted array and a number and you have to find the pair of elements whose sum is closest/near to a givenÂ number

### ALGORITHM

TIME COMPLEXITY:Â O(N)

SPACE COMPLEXITY:Â O(1)

1. We initialize two pointer like variable left and right which point at the start and at the end ofÂ the sorted array respectively.

2. We take closest variable which stores the absolute minimum deviation from a given numberÂ X and another variable called closest_sum which stores the actual nearest sum to X.

3. We loop through the array as follows:

a. sum = arr[left] + arr[right]

b. if abs(sum â€“ X) is less than present closest then update it and also store sum inÂ closest_sum.

c. else check if sum &gt; X then decrease the right variable

d. else if the sum &lt;= X then increase the left variable.

INPUT:

Array: 4 16 28 37 42 56 63 89 124 245

Number: 101

OUTPUT:

100 (sum of 63 and 37)

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[]= {14,16,19,21,46,84,126,169};
int N = sizeof(arr)/sizeof(arr[0]);

int x;
cin>>x; // the number to which closest sum is to be found

//left and right pointing at start and end of the sorted array
int left = 0, right = N-1, sum = 0, closest = INT_MAX , closest_sum;

//sum to store sum , closest to store the minimum difference found and closest_sum to store the actual value closest to x
while(left < right)
{
sum = arr[left] + arr[right];
if(abs(x -sum) < closest)
{
closest = abs(x -sum);
closest_sum = sum;
}
if(sum > x)
right--;
else if(sum <= x)
left++;
}
cout<<closest_sum<<endl;
}``````

Previous articleMost repeating character in a string
If you have come this far, it means that you liked what you are reading. I am a software developer (graduated from BITS Pilani). I love writing technical articles on programming and data structures.