How to find two element whose sum is closet to zero ?
How to find two element whose sum is closet to zero ?
- Element whose sum is closet to zero is also called minimum absolute sum pair. An array of integers, containing both +ve and -ve numbers.
- To find the two elements such that their sum is closest to zero. For example -1 to 1
Method 1:
- To find the sum of it with every other element in the array and compare sums.
- Finally, return the minimum sum.
Sample Code
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
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)
{
printf("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;
}
}
}
printf(" The two elements whose sum is minimum are %d and %d",
arr[min_l], arr[min_r]);
}
/* Driver program to test above function */
int main()
{
int arr[] = {10, 20, -10, 78, -80, 85,-92};
minAbsSumPair(arr, 7);
getchar();
return 0;
}
Output:
The two elements whose sum is minimum are 10 and -10
Method 2
- Sort all the elements of input array.
- Keep 2 index variables for left and right index.
- Initialize: left index l = 0. r = n-1.
- sum = a[l]+a[r]
- If sum is negative than l++ else r - .
- Keep track of absolute min sum.
- Repeat steps 4,5,6 until l < r
Sample Code
# include <stdio.h>
# include <math.h>
# include <limits.h>
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)
{
printf("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--;
}
printf(" The two elements whose sum is minimum are %d and %d",
arr[min_l], arr[min_r]);
}
/* Driver program to test above function */
int main()
{
int arr[] = {20, 50, 10, -30, -65, 65};
int n = sizeof(arr)/sizeof(arr[0]);
minAbsSumPair(arr, n);
getchar();
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 -65 and 65