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]
Posted by
Labels: ,