Problem
Given two sorted arrays and an integer
X
,
find one number from each array such that the sum of these two numbers is the lowest possible.
Approach 1
Since the arrays are sorted, we can decrement values one by one from the first array and find the remaining element in the second array. For example, if the first array is
[1, 2, 3]
and
X
is
20
, then we first decrement
20
by
1
, then by
2
and then by
3
. In each of these, we are left with
19
,
18
and
17
respectively. We then find the closest number to
19
in the second array using binary search.
The closest number to decremented value is either the index at the upper bound or a number at an index one less than the upper bound. Note that if the upper bound is at the starting index of the array, then we don't check the index before it. Think something similar if the upper bound is outside our array. This approach takes O(NlogN) time.
C++ Programming
#include<bits/stdc++.h>
using namespace std;
void solve(int arr[], int brr[], int n, int m, int x)
{
int ans = INT_MAX;
int sum = INT_MAX;
int f,s;
int xx = x;
for(int i=0;i<n;i++){
x-=arr[i];
auto ind = upper_bound(brr, brr+m, x);
int element;
if((ind-brr)>=m) element = brr[m-1];
else{
if(ind!=brr){
auto ind2=ind;
ind2--;
if(abs((brr[ind-brr]+arr[i])-xx)<=abs((brr[ind2-brr]+arr[i])-xx))
element = brr[ind-brr];
else
element = brr[ind2-brr];
}
else element = brr[ind-brr];
}
if(abs((element+arr[i])-xx)<ans){
ans = abs((element+arr[i])-xx);
s = element;
f = arr[i];
sum = element+arr[i];
}
if(abs((element+arr[i])-xx)==ans){
if(element+arr[i]<sum){
s = element;
f = arr[i];
sum = element+arr[i];
}
}
x+=arr[i];
}
cout<<f<<" "<<s;
}
int main(){
int arr[4] = {1, 4, 5, 7};
int brr[4] = {10, 20, 30, 40};
int m = sizeof(arr)/sizeof(arr[0]);
int n = sizeof(brr)/sizeof(brr[0]);
int x = 32;
solve(arr, brr, m, n, x);
}
Output
1
30
Approach 2
We can also use a two-pointer approach to solve this problem. Initialize one pointer to the start of the first array and the second pointer to the end of the second array. Three cases can occur:
Case1:
If the absolute difference between
X
and the
sum of pairs
is smaller than the maximum difference so far, update the answer.
Case2: If the sum of elements is smaller than the given sum, increment the pointer of the first array.
Case 3: If the sum of elements is greater than the given sum, decrement the pointer to the second array.
Python Programming
import sys
def solve(ar1, ar2, m, n, x):
dif=sys.maxsize
l = 0
r = n-1
left=1
right=1
while(l < m and r >= 0):
if abs(ar1[l] + ar2[r] - x) < dif:
left = l
right = r
dif = abs(ar1[l] + ar2[r] - x)
if ar1[l] + ar2[r] > x:
r=r-1
else:
l=l+1
print(ar1[left])
print(ar2[right])
ar1 = [1, 4, 5, 7]
ar2 = [10, 20, 30, 40]
m = len(ar1)
n = len(ar2)
x = 32
solve(ar1, ar2, m, n, x)
Output
1
30
C# Programming
using System;
class Solution {
static void solve(int []ar1,
int []ar2, int m, int n, int x)
{
int dif = int.MaxValue;
int left = 0, right = 0;
int l = 0, r = n-1;
while (l < m && r >= 0)
{
if (Math.Abs(ar1[l] +
ar2[r] - x) < dif)
{
left = l;
right = r;
dif = Math.Abs(ar1[l]
+ ar2[r] - x);
}
if (ar1[l] + ar2[r] > x)
r--;
else
l++;
}
Console.WriteLine(ar1[left]);
Console.Write(ar2[right]);
}
public static void Main()
{
int []ar1 = {1, 4, 5, 7};
int []ar2 = {10, 20, 30, 40};
int m = ar1.Length;
int n = ar2.Length;
int x = 32;
solve(ar1, ar2, m, n, x);
}
}
Output
1
30
People are also reading:
Leave a Comment on this Post