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

  1. Sort all the elements of input 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

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

Related Searches to How to find two element whose sum is closet to zero ?