Sum of two elements whose sum is closest to zero

Last Updated : 01 May, 2024

Given an integer array of N elements. You need to find the maximum sum of two elements such that sum is closest to zero.

Note: In Case if we have two of more ways to form sum of two elements closest to zero return the maximum sum.

Example:

Input: N = 3, arr[] = {-8 -66 -60}
Output: -68
Explanation: Sum of two elements closest to zero is -68 using numbers -60 and -8.

Input: N = 6, arr[] = {-21 -67 -37 -18 4 -65}
Output: -14
Explanation: Sum of two elements closest to zero is -14 using numbers -18 and 4.

Two elements whose sum is closest to zero using Nested Loops:

We use the brute-force method that checks the sum of every possible pair of elements in the array and keeps track of the pair with the minimum absolute sum.

Step-by-step approach:

Initialize variables min_l and min_r to represent the indices of the pair with the minimum sum.
Initialize min_sum with the sum of the first two elements (arr[0] + arr[1]).
Run a loop l from 0 to n-1.
- Run a loop r from l+1 to n.
  - For each pair of indices (l, r), calculate the sum of the corresponding elements (arr[l] + arr[r]).
  - If the absolute value of the calculated sum is less than the absolute value of min_sum, update min_sum, min_l, and min_r with the current sum and indices.
After completing the iteration, return the sum of the pair with indices min_l and min_r.

Below is the implementation of the above approach:

C++

// C++ code to find Two elements
// whose sum is closest to zero
#include <bits/stdc++.h>
using namespace std;

// Function to find the two elements whose sum is closest to
// zero
int minAbsSumPair(int arr[], int n)
{
    // Initialize left and right pointers, minimum sum, sum,
    // and minimum left and right indices
    int l, r, min_sum, sum, min_l, min_r;

    // Initialize minimum sum with the sum of the first two
    // elements
    min_l = 0;
    min_r = 1;
    min_sum = arr[0] + arr[1];

    // Loop through the array
    for (l = 0; l < n - 1; l++) {
        // Inner loop to find the element with the minimum
        // sum
        for (r = l + 1; r < n; r++) {
            // Calculate the sum of the current pair
            sum = arr[l] + arr[r];

            // If the absolute value of the current sum is
            // less than the absolute value of the minimum
            // sum
            if (abs(min_sum) > abs(sum)) {
                // Update the minimum sum, minimum left and
                // right indices
                min_sum = sum;
                min_l = l;
                min_r = r;
            }
        }
    }

    // Return the sum of the two elements with the minimum
    // sum
    return arr[min_l] + arr[min_r];
}

// Driver Code
int main()
{
    // Array of elements
    int arr[] = { 1, 60, -10, 70, -80, 85 };

    // Find the two elements with the minimum sum
    int result = minAbsSumPair(arr, 6);

    // Print the result
    cout << result << endl;

    return 0;
}

Java

import java.util.Arrays;

public class Main {
    // Function to find the two elements whose sum is closest to zero
    static int minAbsSumPair(int[] arr) {
        int n = arr.length;

        // Sort the array to simplify the process
        Arrays.sort(arr);

        // Initialize pointers and minimum sum
        int l = 0, r = n - 1;
        int min_sum = Integer.MAX_VALUE;
        int min_l = 0, min_r = 0;

        // Loop through the array
        while (l < r) {
            // Calculate the current sum
            int sum = arr[l] + arr[r];

            // If the absolute value of the current sum is
            // less than the minimum sum found so far
            if (Math.abs(sum) < Math.abs(min_sum)) {
                // Update the minimum sum and indices
                min_sum = sum;
                min_l = l;
                min_r = r;
            }

            // Move pointers based on the sum
            if (sum < 0) {
                l++;
            } else if (sum > 0) {
                r--;
            } else {
                break; // Found a pair with sum zero
            }
        }

        // Return the sum of the two elements with the minimum sum
        return arr[min_l] + arr[min_r];
    }

    // Driver code
    public static void main(String[] args) {
        // Array of elements
        int[] arr = { 1, 60, -10, 70, -80, 85 };

        // Find the two elements with the minimum sum
        int result = minAbsSumPair(arr);

        // Print the result
        System.out.println(result);
    }
}

// This code is contributed by shivamgupta0987654321

Python

# Function to find the two elements whose sum is closest to zero
def minAbsSumPair(arr):
    # Initialize left and right pointers, minimum sum, sum,
    # and minimum left and right indices
    l, r, min_sum, min_l, min_r = 0, 1, arr[0] + arr[1], 0, 1

    # Loop through the array
    for l in range(len(arr) - 1):
        # Inner loop to find the element with the minimum
        # sum
        for r in range(l + 1, len(arr)):
            # Calculate the sum of the current pair
            sum_pair = arr[l] + arr[r]

            # If the absolute value of the current sum is
            # less than the absolute value of the minimum
            # sum
            if abs(min_sum) > abs(sum_pair):
                # Update the minimum sum, minimum left and
                # right indices
                min_sum = sum_pair
                min_l, min_r = l, r

    # Return the sum of the two elements with the minimum
    # sum
    return arr[min_l] + arr[min_r]

# Driver Code
if __name__ == "__main__":
    # Array of elements
    arr = [1, 60, -10, 70, -80, 85]

    # Find the two elements with the minimum sum
    result = minAbsSumPair(arr)

    # Print the result
    print(result)

JavaScript

// Function to find the two elements whose sum is closest to zero
function minAbsSumPair(arr) {
    const n = arr.length;

    // Sort the array to simplify the process
    arr.sort((a, b) => a - b);

    // Initialize pointers and minimum sum
    let l = 0, r = n - 1;
    let min_sum = Number.MAX_SAFE_INTEGER;
    let min_l = 0, min_r = 0;

    // Loop through the array
    while (l < r) {
        // Calculate the current sum
        const sum = arr[l] + arr[r];

        // If the absolute value of the current sum is
        // less than the minimum sum found so far
        if (Math.abs(sum) < Math.abs(min_sum)) {
            // Update the minimum sum and indices
            min_sum = sum;
            min_l = l;
            min_r = r;
        }

        // Move pointers based on the sum
        if (sum < 0) {
            l++;
        } else if (sum > 0) {
            r--;
        } else {
            break; // Found a pair with sum zero
        }
    }

    // Return the sum of the two elements with the minimum sum
    return arr[min_l] + arr[min_r];
}

// Driver code
const arr = [1, 60, -10, 70, -80, 85];

// Find the two elements with the minimum sum
const result = minAbsSumPair(arr);

// Print the result
console.log(result);

// This code is contributed by shivamgupta0987654321

Output

Time complexity: O(n²)
Auxiliary Space: O(1)

Two elements whose sum is closest to zero using Sorting:

Sort the given array, try two pointer algorithm to find sum closest to zero, we adjust the pointer according to the current sum.

Sort the given array.
Initialize two pointers i and j at the beginning and end of the sorted array, respectively.
Initialize variables sum equal to arr[i] + arr[j] and diff equal to absolute of sum.
While i is less than j:
- Calculate the current sum as arr[i] + arr[j].
- If the current sum is equal to zero, return 0, as this is the closest possible sum.
- If the absolute value of the current sum is less than the absolute value of diff, update diff and sum with the current sum.
- If the absolute value of the current sum is equal to the absolute value of diff, update sum to be the maximum of the current sum and the previous sum.
- If arr[i] + arr[j] is less than 0 then decrement j by 1 else increment i by 1.
After completing the iteration, return the final sum, which represents the maximum sum of two elements closest to zero.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;

int closestToZero(int arr[], int n)
{

    // sorting the array in ascending order
    sort(arr, arr + n);

    int i = 0, j = n - 1;

    // initializing sum with the first and last elements
    int sum = arr[i] + arr[j];

    // initializing the result with the absolute value of
    // the initial sum
    int diff = abs(sum);

    while (i < j) {

        // if we have zero sum, there's no result better.
        // Hence, we return
        if (arr[i] + arr[j] == 0)
            return 0;

        // if we get a better result, we update the
        // difference
        if (abs(arr[i] + arr[j]) < abs(diff)) {
            diff = (arr[i] + arr[j]);
            sum = arr[i] + arr[j];
        }
        else if (abs(arr[i] + arr[j]) == abs(diff)) {

            // if there are multiple pairs with the same
            // minimum absolute difference, return the pair
            // with the larger sum
            sum = max(sum, arr[i] + arr[j]);
        }

        // if the current sum is greater than zero, we
        // search for a smaller sum
        if (arr[i] + arr[j] > 0)
            j--;
        // else, we search for a larger sum
        else
            i++;
    }
    return sum;
}

// Driver Code
int main()
{
    int arr[] = { 1, 60, -10, 70, -80, 85 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = closestToZero(arr, n);

    cout << result;
    return 0;
}

Java

import java.util.Arrays;

public class ClosestToZero {

    public static int closestToZero(int[] arr)
    {
        // Sorting the array in ascending order
        Arrays.sort(arr);

        int i = 0, j = arr.length - 1;

        // Initializing sum with the first and last elements
        int sum = arr[i] + arr[j];

        // Initializing the result with the absolute value
        // of the initial sum
        int diff = Math.abs(sum);

        while (i < j) {
            // If we have zero sum, there's no result
            // better. Hence, we return 0.
            if (arr[i] + arr[j] == 0)
                return 0;

            // If we get a better result, we update the
            // difference
            if (Math.abs(arr[i] + arr[j])
                < Math.abs(diff)) {
                diff = (arr[i] + arr[j]);
                sum = arr[i] + arr[j];
            }
            else if (Math.abs(arr[i] + arr[j])
                     == Math.abs(diff)) {
                // If there are multiple pairs with the same
                // minimum absolute difference, return the
                // pair with the larger sum
                sum = Math.max(sum, arr[i] + arr[j]);
            }

            // If the current sum is greater than zero, we
            // search for a smaller sum
            if (arr[i] + arr[j] > 0)
                j--;
            // Else, we search for a larger sum
            else
                i++;
        }
        return sum;
    }

    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 60, -10, 70, -80, 85 };
        int result = closestToZero(arr);
        System.out.println(result);
    }
}

Python

def closest_to_zero(arr):
    # Sorting the array in ascending order
    arr.sort()

    i, j = 0, len(arr) - 1

    # Initializing sum with the first and last elements
    sum_val = arr[i] + arr[j]

    # Initializing the result with the absolute value
    # of the initial sum
    diff = abs(sum_val)

    while i < j:
        # If we have zero sum, there's no result
        # better. Hence, we return 0.
        if arr[i] + arr[j] == 0:
            return 0

        # If we get a better result, we update the
        # difference
        if abs(arr[i] + arr[j]) < abs(diff):
            diff = arr[i] + arr[j]
            sum_val = arr[i] + arr[j]
        elif abs(arr[i] + arr[j]) == abs(diff):
            # If there are multiple pairs with the same
            # minimum absolute difference, return the
            # pair with the larger sum
            sum_val = max(sum_val, arr[i] + arr[j])

        # If the current sum is greater than zero, we
        # search for a smaller sum
        if arr[i] + arr[j] > 0:
            j -= 1
        # Else, we search for a larger sum
        else:
            i += 1

    return sum_val


# Driver Code
arr = [1, 60, -10, 70, -80, 85]
result = closest_to_zero(arr)
print(result)

JavaScript

function closestToZero(arr) {
    // Sorting the array in ascending order
    arr.sort((a, b) => a - b);

    let i = 0, j = arr.length - 1;

    // Initializing sum with the first and last elements
    let sum = arr[i] + arr[j];

    // Initializing the result with the absolute value
    // of the initial sum
    let diff = Math.abs(sum);

    while (i < j) {
        // If we have zero sum, there's no result
        // better. Hence, we return 0.
        if (arr[i] + arr[j] === 0)
            return 0;

        // If we get a better result, we update the
        // difference
        if (Math.abs(arr[i] + arr[j]) < Math.abs(diff)) {
            diff = arr[i] + arr[j];
            sum = arr[i] + arr[j];
        } else if (Math.abs(arr[i] + arr[j]) === Math.abs(diff)) {
            // If there are multiple pairs with the same
            // minimum absolute difference, return the
            // pair with the larger sum
            sum = Math.max(sum, arr[i] + arr[j]);
        }

        // If the current sum is greater than zero, we
        // search for a smaller sum
        if (arr[i] + arr[j] > 0)
            j--;
        // Else, we search for a larger sum
        else
            i++;
    }
    return sum;
}

// Example usage
let arr = [1, 60, -10, 70, -80, 85];
let result = closestToZero(arr);
console.log(result);

Output

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

GeeksforGeeks

Improve

Count 1's in a sorted binary array

Find a pair with the given difference

Most Common Searching Algorithms

Other Searching Algorithms

Comparisons between Searching Algorithms

Library implementations of Searching algorithms

Easy problems on Searching algorithms

Medium problems on Searching algorithms

Hard problems on Searching algorithms

Sum of two elements whose sum is closest to zero

Two elements whose sum is closest to zero using Nested Loops:

Two elements whose sum is closest to zero using Sorting:

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?