[5 Aug 2020]Two elements whose sum is closest to zero

 

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.

# 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;

}

  

The two elements whose sum is minimum are -80 and 85

Time complexity: O(n^2)

Algorithm
1) Sort all the elements of the input array using their absolute values.
2) Check absolute sum of arr[i-1] and arr[i] if their absolute sum is less than min update min with their absolute value.
3) 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;     // This code is contributed by ceeyesharish }

Output:

The two elements whose sum is minimum are -80 and 85

Time Complexity: O(nlogn)
Space Complexity: O(1)