Given a sorted array and a number x, find the pair in array whose sum is closest to x

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Problem :

Given a sorted array,we need to find a pair whose sum is closed to number X in Array.
For example:

Solution :

Solution 1:

You can check each and every pair of numbers and find the sum close to X.
Java code:

 Solution 2:

  • We will maintain two indexes one at beginning (l=0) and one at end (r=n-1)
  • iterate until l <  r
  • Calculate diff as arr[l] + arr[r]-x
  • if abs (diff) < minDiff then update the minimum sum and pair.
  • If arr[l] + arr[r] is less than X, this means if we want to find sum close to X, do r–
  • If arr[l] + arr[r] is greater than 0,this means if we want to find sum close to X , do l++
Java code:

Time complexity : O(NLogN)

Java program to find a pair whose sum is closest to X:

When you run above program, you will get below output:

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *