# C Program to Find a Pair Whose Sum is Closest to Zero

• Write a program to find a pair whose sum is closest to zero.
• Algorithm to find a pair of number whose sum is nearest to zero.

Given an integer array of size N containing both positive and negative elements. We have to find a pair of elements whose some is closest to zero.
For Example :

```Input Array : -14 40 35 -56 -25 24 70 -60 5 -20
Pair : [-25, 24]
```

Let inputArray be an integer array of size N.

Using Brute Force
• Using two loops, find the sum of each possible pairs of elements and return a pair whose sum is closest to 0.
Time Complexity : O(n2)

## C program to print a pair whose sum is closest to zero

```#include <stdio.h>
#include <math.h>
#include <stdlib.h>

/* Prints a pair of array elements
whose sum is closest to 0 */
void printMinSumPair(int *array, int size){
int i, j, sum, minSum, minPairOne, minPairTwo;

/* Input Validation */
if(array == NULL || size < 2)
return;
/* For every element array[i] find it's sum with
every other element array[j](i < j < size) */
minPairOne = array[0];
minPairTwo = array[1];
minSum = minPairOne + minPairTwo;

for(i = 0; i < size-1; i++) {
for(j = i+1; j < size; j++) {
sum = array[i] + array[j];
if(abs(sum) < abs(minSum)) {
minSum = sum;
minPairOne = array[i];
minPairTwo = array[j];
}
}
}

printf("[%d, %d]\n", minPairOne, minPairTwo);
}

int main(){
int array[10] = {-14, 40, 35, -56, -25, 24, 70, -60, 5, -20};
int i;

printf("Array\n");
for(i = 0; i<10; i++){
printf("%d ", array[i]);
}

printf("\nMinimum Sum Pair\n");
printMinSumPair(array, 10);

return 0;
}
```
Output
```Array
-14 40 35 -56 -25 24 70 -60 5 -20
Minimum Sum Pair
[-25, 24]
```

By Sorting Input Array
• Sort inputArray using any nLogn average time sorting algorithm like quick sort, merge sort etc.
• Initialize left and right to 0 and N-1.
• Find the sum of inputArray[left] and inputArray[right]. Let it be "sum".
• If Compare the sum with the cum of closest zero pair found till now and update it accordingly.
• If sum is < 0 then we have to increase the sum of pair hence increment left.
• If is sum > 0 then we have to reduce the sum of pair hence decrement right.
• Continue above steps until left < right.
Time Complexity : O(nLogn)

## C program to find a pair whose sum is closest to zero using sorting

```#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

/* Swap array element at index left and right */
void swap(int array[], int left, int right) {
int temp;
/* Swapping using a temp variable */
temp = array[left];
array[left]=array[right];
array[right]=temp;
}

void quickSort(int array[], int left, int right) {
int pivot;
if (right > left) {
/* Partition the given array into
two segment by calling partion function */
pivot = partition(array, left, right);

/* Recursively sort left and right sub array*/
quickSort(array, left, pivot-1);
quickSort(array, pivot+1, right);
}
}

int partition(int array[], int left, int right) {
int temp = left;
int pivot = array[left];

while(left < right) {
/* From left side, search for a number
greater than pivot element */
while(array[left] <= pivot)
left++;
/* From right side, search for a number
less than pivot element */
while(array[right] > pivot)
right--;

/*Swap array[left] and array[right] */
if(left < right)
swap(array, left, right);
}
/* Put pivot element in it's currect position '*/
array[temp] = array[right];
array[right] = pivot;
/* Return partition index. All elements left of
right index is < pivot whereas elements right
side of right index are > pivot element */
return right;
}
/* Prints a pair of array elements
whose sum is closest to 0 */
void printMinSumPair(int *array, int size) {
int left, right, sum, minSum, minPairOne, minPairTwo;

/* Sort elements of array using quick sort algorithm  */
quickSort(array, 0, size-1);

/* Initialize left and right to first and
last index of array */
left = 0;
right = size-1;
minSum = INT_MAX;
while(left < right) {
sum = array[left] + array[right];
/*Check if sum of array[left] and array[right]
is less than to minSum */
if(abs(sum) < abs(minSum)) {
minSum = sum;
minPairOne = array[left];
minPairTwo = array[right];
}

if(sum < 0) {
/* If sum < 0, then increase the value
of sum by incrementing left index */
left++;
} else {
/* sum is greater than 0, decrease
value of sum by decrementing right index */
right--;
}
}
printf("[%d, %d]\n", minPairOne, minPairTwo);
}

int main(){
int i, array[100], count;
printf("Enter the number of elements in Array\n");
scanf("%d", &count);

printf("Enter %d numbers\n", count);
for(i = 0; i < count; i++){
scanf("%d", &array[i]);
}

printf("\nMinimum Sum Pair\n");
printMinSumPair(array, count);

return 0;
}
```
Output
```Enter the number of elements in Array
10
Enter 10 numbers
-14 40 35 -56 -25 24 70 -60 5 -20

Minimum Sum Pair
[-25, 24]
```