Given a sorted array and a number x, find a pair in array whose sum is closest to x.
Examples:
Input: arr[] = {10, 22, 28, 29, 32, 40}, x = 54
Output: 22 and 32
A simple solution is to consider every pair and keep track of closest pair (absolute difference between pair sum and x is minimum). Finally print the closest pair. Time complexity of this solution is O(n2)
An efficient solution can find the pair in O(n) time. The idea is similar to method 2 of this post. Following is detailed algorithm.
#include <iostream>
#include <climits>
#include <cstdlib>
using namespace std;
// Prints the pair with sum cloest to x
void printClosest(int arr[], int n, int x)
{
int res_l, res_r;
int l = 0, r = n-1, diff = INT_MAX;
while (r > l)
{
if (abs(arr[l] + arr[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = abs(arr[l] + arr[r] - x);
}
if (arr[l] + arr[r] > x)
r--;
else
l++;
}
cout <<" The closest pair is " << arr[res_l] << " and " << arr[res_r];
}
int main()
{
int arr[] = {10, 22, 28, 29, 32, 40}, x = 54;
int n = sizeof(arr)/sizeof(arr[0]);
printClosest(arr, n, x);
return 0;
}
See Running code at http://ideone.com/q3F4OQ