Find pair in an array having minimum absolute sum

Given an sorted array of integers, find a pair in it having minimum absolute sum.

 

For example,


Input:  A = [-6, -5, -3, 0, 2, 4, 9]

Output: Pair is (-5, 4)

(-5, 4) = abs(-5 + 4) = abs(-1) = 1, which is minimum among all pairs.

 
 

The idea is to maintain search space by maintaining two indexes (low and high) that initially points to two end-points of the array. Then we loop till low is less than high index and reduce search space arr[low..high] at each iteration of the loop by comparing sum of elements present at index low and high with 0. We increment index low if sum is less than the 0 else we decrement index high is sum is more than the 0. We also maintain the minimum absolute difference among all pairs present at low and high index.

C++

Download   Run Code

Output:

Pair found (-5, 4)

Java

Download   Run Code

Output:

Pair found (-5, 4)

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)
Loading...

 
Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Mirwise Khan
Guest

// Here is my solution

#include “stdio.h”
#include “math.h”

int main(){

int a[] = {-6, -5, -3, 0, 2, 4, 9};
int size = sizeof(a)/sizeof(a[0]);

// Save min as the sum of first two values

int min = abs(a[0] + a[1]);

// The b array is for the final pair answer

int b[2];

// Compare each number with the series of numbers after it

for(int i = 0; i < size; i++){
for(int j = i+1; j abs(a[i]+a[j])){
b[0] = a[i];
b[1] = a[j];
min = abs(a[i]+a[j]);
}
}
}

printf(“\n\n MiNiMUM (%d,%d) = %d”, b[0], b[1], abs(b[0]+b[1]));

Ankur Maheshwari
Guest

This can be optimized using binary search finding transition from negative to positive. In other cases(all +ves or _-ves) its the return of first two and last two respectively.