Question: An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.
For the below array, program should print -80 and 85.
METHOD 1 (Simple)
For each element, find the sum of it with every other element in the array and compare sums. Finally, return the minimum sum.
Implementation:
// C++ code to find Two elements
// whose sum is closest to zero
# include <bits/stdc++.h>
# include <stdlib.h> /* for abs() */
# include <math.h>
using namespace std;
void minAbsSumPair( int arr[], int arr_size)
{
int inv_count = 0;
int l, r, min_sum, sum, min_l, min_r;
/* Array should have at least
two elements*/
if (arr_size < 2)
{
cout << "Invalid Input" ;
return ;
}
/* Initialization of values */
min_l = 0;
min_r = 1;
min_sum = arr[0] + arr[1];
for (l = 0; l < arr_size - 1; l++)
{
for (r = l + 1; r < arr_size; r++)
{
sum = arr[l] + arr[r];
if ( abs (min_sum) > abs (sum))
{
min_sum = sum;
min_l = l;
min_r = r;
}
}
}
cout << "The two elements whose sum is minimum are "
<< arr[min_l] << " and " << arr[min_r];
}
// Driver Code
int main()
{
int arr[] = {1, 60, -10, 70, -80, 85};
minAbsSumPair(arr, 6);
return 0;
}
Output:
The two elements whose sum is minimum are -80 and 85
Time complexity: O(n^2)
METHOD 2 (Use Sorting):
Algorithm
- Sort all the elements of the input array.
- Use two index variables l and r to traverse from left and right ends respectively. Initialize l as 0 and r as n-1.
- sum = a[l] + a[r]
- If sum is -ve, then l++
- If sum is +ve, then r–
- Keep track of abs min sum.
- Repeat steps 3, 4, 5 and 6 while l < r
Implementation
#include <bits/stdc++.h>
using namespace std;
void quickSort( int *, int , int );
/* Function to print pair of elements
having minimum sum */
void minAbsSumPair( int arr[], int n)
{
// Variables to keep track
// of current sum and minimum sum
int sum, min_sum = INT_MAX;
// left and right index variables
int l = 0, r = n-1;
// variable to keep track of
// the left and right pair for min_sum
int min_l = l, min_r = n-1;
/* Array should have at least two elements*/
if (n < 2)
{
cout << "Invalid Input" ;
return ;
}
/* Sort the elements */
quickSort(arr, l, 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--;
}
cout << "The two elements whose sum is minimum are "
<< arr[min_l] << " and " << arr[min_r];
}
// Driver Code
int main()
{
int arr[] = {1, 60, -10, 70, -80, 85};
int n = sizeof (arr) / sizeof (arr[0]);
minAbsSumPair(arr, n);
return 0;
}
/* FOLLOWING FUNCTIONS ARE ONLY FOR
SORTING PURPOSE */
void exchange( int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition( int arr[], int si, int ei)
{
int x = arr[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++)
{
if (arr[j] <= x)
{
i++;
exchange(&arr[i], &arr[j]);
}
}
exchange (&arr[i + 1], &arr[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
arr[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort( int arr[], int si, int ei)
{
int pi; /* Partitioning index */
if (si < ei)
{
pi = partition(arr, si, ei);
quickSort(arr, si, pi - 1);
quickSort(arr, pi + 1, ei);
}
}
Output:
The two elements whose sum is minimum are -80 and 85
Time Complexity: complexity to sort + complexity of finding the optimum pair = O(nlogn) + O(n) = O(nlogn)
STL implementation of Method-2:
Algorithm
- Sort all the elements of the input array using their absolute values.
- Check absolute sum of arr[i-1] and arr[i] if their absolute sum is less than min update min with their absolute value.
- Use two variables to store the index of the elements.
Implementation
// C++ implementation using STL
#include <bits/stdc++.h>
using namespace std;
// Modified to sort by abolute values
bool compare( int x, int y)
{
return abs (x) < abs (y);
}
void findMinSum( int arr[], int n)
{
sort(arr, arr + n, compare);
int min = INT_MAX, x, y;
for ( int i = 1; i < n; i++) {
// Absolute value shows how close it is to zero
if ( abs (arr[i - 1] + arr[i]) <= min) {
// if found an even close value
// update min and store the index
min = abs (arr[i - 1] + arr[i]);
x = i - 1;
y = i;
}
}
cout << "The two elements whose sum is minimum are "
<< arr[x] << " and " << arr[y];
}
// Driver code
int main()
{
int arr[] = { 1, 60, -10, 70, -80, 85 };
int n = sizeof (arr) / sizeof (arr[0]);
findMinSum(arr, n);
return 0;
}
Output:
The two elements whose sum is minimum are -80 and 85
Time Complexity: O(nlogn)
Space Complexity: O(1)