# 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(n2)

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)).