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

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

Preparation

What's New

Top Interview Coding Problems/Challenges!