Given two sorted arrays and a number x, find the pair whose sum is closest to x and the pair has an element from each array.
We are given two arrays ar1[0…m-1] and ar2[0..n-1] and a number x, we need to find the pair ar1[i] + ar2[j] such that absolute value of (ar1[i] + ar2[j] – x) is minimum.
Example:
Input: ar1[] = {1, 4, 5, 7};
ar2[] = {10, 20, 30, 40};
x = 32
Output: 1 and 30
Input: ar1[] = {1, 4, 5, 7};
ar2[] = {10, 20, 30, 40};
x = 50
Output: 7 and 40
PHP
<?php// PHP program to find the pair // from two sorted arrays such// that the sum of pair is // closest to a given number x// ar1[0..m-1] and ar2[0..n-1] // are two given sorted arrays// and x is given number. This// function prints the pair from// both arrays such that the sum// of the pair is closest to x.function printClosest($ar1, $ar2, $m, $n, $x){ // Initialize the diff between // pair sum and x. $diff = PHP_INT_MAX; // res_l and res_r are result // indexes from ar1[] and ar2[] // respectively $res_l; $res_r; // Start from left side of // ar1[] and right side of ar2[] $l = 0; $r = $n - 1; while ($l < $m and $r >= 0) { // If this pair is closer to // x than the previously // found closest, then // update res_l, res_r and // diff if (abs($ar1[$l] + $ar2[$r] - $x) < $diff) { $res_l = $l; $res_r = $r; $diff = abs($ar1[$l] + $ar2[$r] - $x); } // If sum of this pair is // more than x, move to smaller // side if ($ar1[$l] + $ar2[$r] > $x) $r--; // move to the greater side else $l++; } // Print the result echo "The closest pair is [", $ar1[$res_l], ", ", $ar2[$res_r], "] \n";} // Driver Code $ar1 = array(1, 4, 5, 7); $ar2 = array(10, 20, 30, 40); $m = count($ar1); $n = count($ar2); $x = 38; printClosest($ar1, $ar2, $m, $n, $x);// This code is contributed by anuj_67.?> |
Output:
The closest pair is [7, 30]
Time Complexity : O(m+n) i.e. linear.
Auxiliary Space : O(1)
Please refer complete article on Find the closest pair from two sorted arrays for more details!
