How to find a pair of numbers in the array which sum is closest to x with O(n) time complexity?

user_11080485 0
Viewed 145

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));

time-complexity algorithm javascript
2 Answers

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.

user_37961130

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));

user_110804850
Related