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

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 > 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;
}
Try It

 


Next > < Prev
Scroll to Top