• Jobs
  • About Us
  • professionals
    • Home
    • Jobs
    • Courses and challenges
    • Questions
    • Teachers
  • business
    • Home
    • Post vacancy
    • Our process
    • Pricing
    • Assessments
    • Payroll
    • Blog
    • Sales
    • Salary Calculator

0

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

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

almost 3 years ago · Juan Pablo Isaza
2 answers
Answer question

0

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.

almost 3 years ago · Juan Pablo Isaza Report

0

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

almost 3 years ago · Juan Pablo Isaza Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Our process Sales
Legal
Terms and conditions Privacy policy
© 2025 PeakU Inc. All Rights Reserved.

Andres GPT

Recommend me some offers
I have an error