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++ implementation –
 

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

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Mirwise Khan
Guest
Mirwise Khan

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

wpDiscuz