Home » Data Structure » Array Data Structure

Two elements whose sum is closest to zero

C++ implementation to find two elements whose sum is closest to zero.
Submitted by Vikneshwar GK, on January 20, 2022

Consider an array of size n and it contains both positive and negative elements. For example, if n=5, the array elements can be like -5, 5, 0, 2, -1. The task at hand is to find any two elements from the array whose sum is closest to zero.

Example:

Input:
test1[] = {-4, 2, 6, 5, -7, -1, 9, -8}

Output:
2 and -1

Explanation:
The sum of 2 and -1 is 1 which is closest to 0 
than the sum of any other element. 
Pairs like (5,-4), (9, -8) are also correct answers 
as their sum is also equal to 1 but since the question 
asks for any 2 pairs, we are going with 2 and -1.

Input:
test1[] = {-3, 10, 8, -2, 2, -1}

Output:
-2 and 2

Explanation:
Sum of -2 and 2 is 0.

Solution 1: Compare all elements

This is a usual approach to solve this problem, i.e., finding the sum of every element with every other element and output the one that is closest to zero.

C++ Implementation:

#include <bits/stdc++.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

// Function to find elements whose sum
// is closest to zero
void closestToZero(int array[], int length)
{
    int sum_min, sum, left_min, right_min;

    // array length check
    // must contain atleast two elements
    if (length < 2) {
        cout << "Invalid Input";
        return;
    }

    // initialize variablees
    left_min = 0;
    right_min = 1;
    sum_min = array[0] + array[1];

    // nested loop to iterate through the array
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++) {
            sum = array[i] + array[j];

            // finding minimum sum
            if (abs(sum_min) > abs(sum)) {
                sum_min = sum;
                left_min = i;
                right_min = j;
            }
        }
    }

    // print the elements
    cout << "Sum closest to zero elements : " << array[left_min] << " and " << array[right_min];
}

int main()
{
    int array[100], N;

    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    closestToZero(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1:-3
Enter element 2:10
Enter element 3:8
Enter element 4:-2
Enter element 5:2
Enter element 6:1
Sum closest to zero elements : -2 and 2

Time Complexity: O(n²)

Solution 2: Sorting the array

This approach involves sorting the array using an O(nlog(n)). Then use two pointers to point the start and end of the array. It involves the following steps:

• Step 1: start=0 and end=length-1
• Step 2: find sum which is the sum of array elements at start and end position
• Step 3: if sum is negative, then increment starts
• Step 4: if sum is positive, then decrement end
• Step 5: Check for minimum sum at every step
• Step 6: Repeat step 2 to step 5 until start >= end

C++ Implementation:

#include <bits/stdc++.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

// Function to find elements whose sum
// is closest to zero
void closestToZero(int array[], int length)
{
    // Initialize variables
    int sum = 0, sum_min = INT_MAX, start = 0, end = length - 1, start_min = 0, end_min = length - 1;

    // array length check
    // must contain atleast two elements
    if (length < 2) {
        cout << "Invalid Input";
        return;
    }

    // sort the elements
    sort(array, array + length);

    while (start < end) {
        sum = array[start] + array[end];

        // finding minimum sum
        if (abs(sum) < abs(sum_min)) {
            sum_min = sum;
            start_min = start;
            end_min = end;
        }
        if (sum < 0)
            start++;
        else
            end--;
    }

    cout << "Sum closest to zero elements: "
         << array[start_min] << " and " << array[end_min];
}

int main()
{
    int array[100], N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    closestToZero(array, N);

    return 0;
}

Output:

Enter Number of elements: 8
Enter element 1:-4
Enter element 2:2
Enter element 3:6
Enter element 4:5
Enter element 5:-7
Enter element 6:-1
Enter element 7:9
Enter element 8:-8
Sum closest to zero elements: -8 and 9

Time Complexity: O(nlog(n))

This approach involves sorting whose time complexity is O(nlog(n)) and although it finds minimum sum with time complexity of O(n), the overall time complexity remains O(nlog(n)).