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_landmin_rto represent the indices of the pair with the minimum sum. - Initialize
min_sumwith 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_rwith 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_landmin_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)
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.