Sum of two elements whose sum is closest to zero
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
andmin_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
, updatemin_sum
,min_l
, andmin_r
with the current sum and indices.
- For each pair of indices
- Run a loop r from l+1 to n.
- After completing the iteration, return the sum of the pair with indices
min_l
andmin_r
.
Below is the implementation of the above approach:
// 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;
}
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
# 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)
// 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
5
Time complexity: O(n2)
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
andj
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 thanj
:- 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
, updatediff
andsum
with the current sum. - If the absolute value of the current sum is equal to the absolute value of
diff
, updatesum
to be the maximum of the current sum and the previoussum
. - If arr[i] + arr[j] is less than 0 then decrement j by 1 else increment i by 1.
- Calculate the current sum as
- 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:
#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;
}
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);
}
}
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)
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
5
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Contact Us