Problem: This problem is also called minimum absolute sum pair.
You are given an array of integers, containing both +ve and -ve numbers. You need to find the two elements such that their sum is closest to zero.
eg. Array [15, 5, -20, 30, -45] O/P should be 15, -20
Solution:
Searching for two numbers (not necessarily consecutive) in an array of positive and negative numbers whose sum is closest to zero? What is the best possible algorithm that comes to your mind?
O(n^2) ?
For each element, find the sum of it with every other element in the array and compare sums. Finally, return the minimum sum. That is simple brute force O(n^2) solution.
Can’t you think up of an O(n lg n) algorithm? Didn’t get hint? Yes, Sorting. See how does sorting will help us.
Steps:
1) Sort all the elements of the array.
2) Keep 2 index variables for left and right index.
3) Initialize: left index l = 0. r = n-1.
4) sum = a[l]+a[r]
5) If sum is negative than l++ else r — .
6) Keep track of absolute min sum.
7) Repeat steps 4,5,6 until l < r
I guess now its easy to implement.
Implementation:
Sorting function (Quick Sort already explained in our previous posts. Quick Sort)
/* Function to print pair of elements having minimum sum */
void minAbsSumPair(int arr[], int n)
{
int l, r , min_sum, sum = 0, min_l, min_r;
/* Array should have at least two elements*/
if(n < 2)
{
printf("Invalid Input");
return;
}
/* Sort the elements */
quickSort(arr, 0, n-1);
/* Start looking for the pair */
l = 0; r = n-1;
min_sum = arr[l] + arr[r];
min_l = l;
min_r = r;
while(l < r)
{
sum = arr[l] + arr[r];
/*If abs(sum) is less then update the result items*/
if(abs(sum) < abs(min_sum))
{
min_sum = sum;
min_l = l;
min_r = r;
}
if(sum < 0)
l++;
else
r--;
}
printf(" The two elements whose sum is minimum are %d and %d",
arr[min_l], arr[min_r]);
}
/* Main program to test above function */
int main()
{
int arr[] = {15, 5, -20, 30, -45};
minAbsSumPair(arr, 5);
getchar();
return 0;
}
Time Complexity: Complexity to sort + complexity of finding the pair = O(nlogn) + O(n) = O(nlogn)
Venkatesh Kotrike ::This is will give u a answer for array {-45, -20, -2, -1, 12, 15, 30}
package javaapplication8;
import static java.lang.Math.abs;
class abc
{
void minAbsSumPair(int arr[], int n)
{
int l, r , min_sum, sum = 0, min_l, min_r;
/* Array should have at least two elements*/
if(n < 2)
{
System.out.println("Invalid Input");
return;
}
/* Sort the elements */
/* Start looking for the pair */
l = 0; r = n-1;
min_sum = arr[l] + arr[r];
min_l = l;
min_r = r;
while(l < r)
{
sum = arr[l] + arr[r];
/*If abs(sum) is less then update the result items*/
if(abs(sum) < abs(min_sum))
{
min_sum = sum;
min_l = l;
min_r = r;
}
if(sum <0)
l++;
else
r–;
}
System.out.println(" The two elements whose sum is minimum are" +arr[min_l]+ "and" +arr[min_r]);
}
}
public class JavaApplication8
{
public static void main(String[] args)
{
abc a =new abc();
int arr[] = {-45, -20, -2, -1, 12, 15, 30};
a.minAbsSumPair(arr, 7);
}
}
private static void findTwoNumWithSumZero(int[] a) {
List list=new ArrayList();
HashMap hm=new HashMap();
for(int i=0;i<a.length;i++){
int sum=0;
for(int j=i+1;j<a.length;j++){
sum=a[i]+a[j];
list.add(Math.abs(sum));
hm.put(Math.abs(sum), i+";"+j);
}
}
Collections.sort(list);
String b[]=hm.get(list.get(0)).split(";");
System.out.println(a[Integer.parseInt(b[0])]);
System.out.println(a[Integer.parseInt(b[1])]);
}
public class MinAbsSum {
public static void main(String[] args) {
int a[]={-45, -20, -2, -1, 12, 15, 30 };
// Let the first two numbers of array be required paired
int p1=a[0],p2=a[1],msum=a[0]+a[1];
/* if sum is negative then make it positive.
Logic is if i convert all "sums" to positive then the smallest
sum would be the one closest to zero*/
if(msum<0)
msum=msum*-1;
int tsum;// temporary sum variable
for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<a.length;j++)
{
tsum=a[i]+a[j]; // adding two elements and storing it in tsum
if(tsum<0)
tsum=tsum*-1;//if sum is negative then make it positive.
//If current sum of elements is less than minimum sum then
// those are the required elements or pair
if(tsum<msum)
{ p1=a[i]; p2=a[j]; msum=tsum;}
}
}
System.out.println("Two elements whose sum is closest to zero are :"+p1+" "+p2);
}
}