Given a sorted array and a number x, find a pair in that array whose sum is closest to x". How can we implement this with O(n) time complexity?
Example:
fn([10,22,28,29,30,40], 54) // => [22, 30]
fn([1,3,4,7,10], 15) // => [4, 10]
fn([5], 7) // => []
fn([], 7) // => []
Update:
It was my latest try to solve this problem, which isn't working and it has O(n^2) time complexity.
function fn(arr, x) {
let res = [];
if (arr.length < 2) return res;
for (let i = 0; i < arr.length - 1; i++) {
for (let j = arr.length - 1; j > i; j--) {
let t = Math.abs(arr[i] + arr[j] - x);
if (arr[i] + arr[j] === x) return (res = [arr[i], arr[j]]);
if (arr[i] + arr[j] > x) {
if (t > Math.abs(arr[i] + arr[j] - x)) {
t = Math.abs(arr[i] + arr[j] - x);
res = [arr[i], arr[j]];
}
}
}
}
return res;
}
console.log(fn([10, 22, 28, 29, 30, 40], 54));
console.log(fn([1, 3, 4, 7, 10], 15));The basic idea is very simple. To follow along from a very safe position, we will first try the farthest numbers.
1 2 3 4 5
^ ^
l r
Now we have different cases. Let's be the difference between the sum of two num and the given number is d
At first we would allow any d. Set it a very large number.
Then if sum of a[l]+a[r] < x then try to increase it? So it would be logical to move towards right of the sorted (ascending array) l++
Else if it is a[l]+a[r] > x, r-- so reduce the sum or move left.
If you are wondering why did I introduce d, maybe think a bit. But yes it is just to store the difference. So it would be absolute value of a[l]+a[r]-x.
To be more precise, you only need to run it till you have l<r.
I solved it in javascript code:
function fn(arr, x) {
let res = [];
if (arr.length < 2) return res;
let i = 0,
j = arr.length - 1,
t = Math.abs(arr[i] + arr[j] - x);
while (i < j) {
let s = arr[i] + arr[j];
if (s === t) {
res = [arr[i], arr[j]];
break;
}
if (s < x) {
i++;
if (Math.abs(arr[i] + arr[j] - x) < t) {
t = Math.abs(arr[i] + arr[j] - x);
res = [arr[i], arr[j]];
}
}
if (s > x) {
j--;
if (Math.abs(arr[i] + arr[j] - x) < t) {
t = Math.abs(arr[i] + arr[j] - x);
res = [arr[i], arr[j]];
}
}
}
return res;
}
console.log(fn([10, 22, 28, 29, 30, 40], 54));
console.log(fn([1, 3, 4, 7, 10], 15));
console.log(fn([5], 7));
console.log(fn([], 7));