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

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 > X then decrease the right variable

d. else if the sum <= 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;
}