Question: An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.
For the below array, program should print -80 and 85.
METHOD 1 (Simple)
For each element, find the sum of it with every other element in the array and compare sums. Finally, return the minimum sum.
Implementation:
C++
// C++ code to find Two elements// whose sum is closest to zero# include <bits/stdc++.h># include <stdlib.h> /* for abs() */# include <math.h>using namespace std;void minAbsSumPair(int arr[], int arr_size){ int inv_count = 0; int l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if(arr_size < 2) { cout << "Invalid Input"; return; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for(l = 0; l < arr_size - 1; l++) { for(r = l + 1; r < arr_size; r++) { sum = arr[l] + arr[r]; if(abs(min_sum) > abs(sum)) { min_sum = sum; min_l = l; min_r = r; } } } cout << "The two elements whose sum is minimum are " << arr[min_l] << " and " << arr[min_r];}// Driver Codeint main(){ int arr[] = {1, 60, -10, 70, -80, 85}; minAbsSumPair(arr, 6); return 0;}// This code is contributed// by Akanksha Rai(Abby_akku) |
C
// C code to find Two elements// whose sum is closest to zero# include <stdio.h># include <stdlib.h> /* for abs() */# include <math.h>void minAbsSumPair(int arr[], int arr_size){ int inv_count = 0; int l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if(arr_size < 2) { printf("Invalid Input"); return; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for(l = 0; l < arr_size - 1; l++) { for(r = l+1; r < arr_size; r++) { sum = arr[l] + arr[r]; if(abs(min_sum) > abs(sum)) { min_sum = sum; min_l = l; min_r = r; } } } printf(" The two elements whose sum is minimum are %d and %d", arr[min_l], arr[min_r]);}/* Driver program to test above function */int main(){ int arr[] = {1, 60, -10, 70, -80, 85}; minAbsSumPair(arr, 6); getchar(); return 0;} |
Java
// Java code to find Two elements// whose sum is closest to zeroimport java.util.*;import java.lang.*;class Main{ static void minAbsSumPair(int arr[], int arr_size) { int inv_count = 0; int l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if(arr_size < 2) { System.out.println("Invalid Input"); return; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for(l = 0; l < arr_size - 1; l++) { for(r = l+1; r < arr_size; r++) { sum = arr[l] + arr[r]; if(Math.abs(min_sum) > Math.abs(sum)) { min_sum = sum; min_l = l; min_r = r; } } } System.out.println(" The two elements whose "+ "sum is minimum are "+ arr[min_l]+ " and "+arr[min_r]); } // main function public static void main (String[] args) { int arr[] = {1, 60, -10, 70, -80, 85}; minAbsSumPair(arr, 6); } } |
Python3
# Python3 code to find Two elements# whose sum is closest to zerodef minAbsSumPair(arr,arr_size): inv_count = 0 # Array should have at least # two elements if arr_size < 2: print("Invalid Input") return # Initialization of values min_l = 0 min_r = 1 min_sum = arr[0] + arr[1] for l in range (0, arr_size - 1): for r in range (l + 1, arr_size): sum = arr[l] + arr[r] if abs(min_sum) > abs(sum): min_sum = sum min_l = l min_r = r print("The two elements whose sum is minimum are", arr[min_l], "and ", arr[min_r])# Driver program to test above function arr = [1, 60, -10, 70, -80, 85]minAbsSumPair(arr, 6);# This code is contributed by Smitha Dinesh Semwal |
C#
// C# code to find Two elements// whose sum is closest to zerousing System;class GFG{static void minAbsSumPair(int []arr, int arr_size) { int l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if (arr_size < 2) { Console.Write("Invalid Input"); return; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for (l = 0; l < arr_size - 1; l++) { for (r = l+1; r < arr_size; r++) { sum = arr[l] + arr[r]; if (Math.Abs(min_sum) > Math.Abs(sum)) { min_sum = sum; min_l = l; min_r = r; } } } Console.Write(" The two elements whose "+ "sum is minimum are "+ arr[min_l]+ " and "+arr[min_r]); } // main function public static void Main () { int []arr = {1, 60, -10, 70, -80, 85}; minAbsSumPair(arr, 6); } }// This code is contributed by Sam007 |
PHP
<?php// PHP program to find the Two elements// whose sum is closest to zerofunction minAbsSumPair($arr, $arr_size){ $inv_count = 0; /* Array should have at least two elements*/ if($arr_size < 2) { echo "Invalid Input"; return; } /* Initialization of values */ $min_l = 0; $min_r = 1; $min_sum = $arr[0] + $arr[1]; for($l = 0; $l < $arr_size - 1; $l++) { for($r = $l+1; $r < $arr_size; $r++) { $sum = $arr[$l] + $arr[$r]; if(abs($min_sum) > abs($sum)) { $min_sum = $sum; $min_l = $l; $min_r = $r; } } } echo "The two elements whose sum is minimum are " .$arr[$min_l]." and ". $arr[$min_r]; }// Driver Code$arr = array(1, 60, -10, 70, -80, 85);minAbsSumPair($arr, 6);// This code is contributed by Sam007?> |
Javascript
<script>// JavaScript code to find Two elements// whose sum is closest to zerofunction minAbsSumPair( arr, arr_size){ var inv_count = 0; var l, r, min_sum, sum, min_l, min_r; /* Array should have at least two elements*/ if(arr_size < 2) { document.write("Invalid Input"); return; } /* Initialization of values */ min_l = 0; min_r = 1; min_sum = arr[0] + arr[1]; for(l = 0; l < arr_size - 1; l++) { for(r = l + 1; r < arr_size; r++) { sum = arr[l] + arr[r]; if(Math.abs(min_sum) > Math.abs(sum)) { min_sum = sum; min_l = l; min_r = r; } } } document.write("The two elements whose sum is minimum are " + arr[min_l] + " and " + arr[min_r]);} // Driver Code arr = new Array(1, 60, -10, 70, -80, 85); minAbsSumPair(arr, 6); // This code is contributed by simranarora5sos</script> |
Output:
The two elements whose sum is minimum are -80 and 85
Time complexity: O(n2)
Auxiliary Space: O(1)
METHOD 2 (Use Sorting):
Algorithm :
- Sort all the elements of the input array.
- Use two index variables l and r to traverse from left and right ends respectively. Initialize l as 0 and r as n-1.
- sum = a[l] + a[r]
- If sum is -ve, then l++
- If sum is +ve, then r–
- Keep track of abs min sum.
- Repeat steps 3, 4, 5 and 6 while l < r
Implementation:
C++
#include <bits/stdc++.h>using namespace std;void quickSort(int *, int, int); /* Function to print pair of elements having minimum sum */void minAbsSumPair(int arr[], int n) { // Variables to keep track // of current sum and minimum sum int sum, min_sum = INT_MAX; // left and right index variables int l = 0, r = n-1; // variable to keep track of // the left and right pair for min_sum int min_l = l, min_r = n-1; /* Array should have at least two elements*/ if(n < 2) { cout << "Invalid Input"; return; } /* Sort the elements */ quickSort(arr, l, r); while(l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if(abs(sum) < abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if(sum < 0) l++; else r--; } cout << "The two elements whose sum is minimum are " << arr[min_l] << " and " << arr[min_r]; } // Driver Codeint main() { int arr[] = {1, 60, -10, 70, -80, 85}; int n = sizeof(arr) / sizeof(arr[0]); minAbsSumPair(arr, n); return 0; } /* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING PURPOSE */void exchange(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int partition(int arr[], int si, int ei) { int x = arr[ei]; int i = (si - 1); int j; for (j = si; j <= ei - 1; j++) { if(arr[j] <= x) { i++; exchange(&arr[i], &arr[j]); } } exchange (&arr[i + 1], &arr[ei]); return (i + 1); } /* Implementation of Quick Sort arr[] --> Array to be sorted si --> Starting index ei --> Ending index */void quickSort(int arr[], int si, int ei) { int pi; /* Partitioning index */ if(si < ei) { pi = partition(arr, si, ei); quickSort(arr, si, pi - 1); quickSort(arr, pi + 1, ei); } } // This code is contributed by rathbhupendra |
C
# include <stdio.h># include <math.h># include <limits.h>void quickSort(int *, int, int);/* Function to print pair of elements having minimum sum */void minAbsSumPair(int arr[], int n){ // Variables to keep track of current sum and minimum sum int sum, min_sum = INT_MAX; // left and right index variables int l = 0, r = n-1; // variable to keep track of the left and right pair for min_sum int min_l = l, min_r = n-1; /* Array should have at least two elements*/ if(n < 2) { printf("Invalid Input"); return; } /* Sort the elements */ quickSort(arr, l, r); while(l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if(abs(sum) < abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if(sum < 0) l++; else r--; } printf(" The two elements whose sum is minimum are %d and %d", arr[min_l], arr[min_r]);}/* Driver program to test above function */int main(){ int arr[] = {1, 60, -10, 70, -80, 85}; int n = sizeof(arr)/sizeof(arr[0]); minAbsSumPair(arr, n); getchar(); return 0;}/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING PURPOSE */void exchange(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp;}int partition(int arr[], int si, int ei){ int x = arr[ei]; int i = (si - 1); int j; for (j = si; j <= ei - 1; j++) { if(arr[j] <= x) { i++; exchange(&arr[i], &arr[j]); } } exchange (&arr[i + 1], &arr[ei]); return (i + 1);}/* Implementation of Quick Sortarr[] --> Array to be sortedsi --> Starting indexei --> Ending index*/void quickSort(int arr[], int si, int ei){ int pi; /* Partitioning index */ if(si < ei) { pi = partition(arr, si, ei); quickSort(arr, si, pi - 1); quickSort(arr, pi + 1, ei); }} |
Java
import java.util.*;import java.lang.*;class Main{ static void minAbsSumPair(int arr[], int n) { // Variables to keep track of current sum and minimum sum int sum, min_sum = 999999; // left and right index variables int l = 0, r = n-1; // variable to keep track of the left and right pair for min_sum int min_l = l, min_r = n-1; /* Array should have at least two elements*/ if(n < 2) { System.out.println("Invalid Input"); return; } /* Sort the elements */ sort(arr, l, r); while(l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if(Math.abs(sum) < Math.abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if(sum < 0) l++; else r--; } System.out.println(" The two elements whose "+ "sum is minimum are "+ arr[min_l]+ " and "+arr[min_r]); } // main function public static void main (String[] args) { int arr[] = {1, 60, -10, 70, -80, 85}; int n = arr.length; minAbsSumPair(arr, n); } /* Functions for QuickSort */ /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ static int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // index of smaller element for (int j=low; j<high; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } /* The main function that implements QuickSort() arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ static void sort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ int pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort(arr, pi+1, high); } }} |
Python3
# Function to print pair of elements# having minimum sum */# FOLLOWING FUNCTIONS ARE ONLY FOR# SORTING PURPOSE */def partition(arr, si, ei): x = arr[ei] i = (si - 1) for j in range(si,ei): if(arr[j] <= x): i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[ei] = arr[ei], arr[i + 1] return (i + 1) # Implementation of Quick Sort# arr[] --> Array to be sorted# si --> Starting index# ei --> Ending indexdef quickSort(arr, si, ei): pi = 0 # Partitioning index */ if(si < ei): pi = partition(arr, si, ei) quickSort(arr, si, pi - 1) quickSort(arr, pi + 1, ei)def minAbsSumPair(arr, n): # Variables to keep track # of current sum and minimum sum sum, min_sum = 0, 10**9 # left and right index variables l = 0 r = n - 1 # variable to keep track of # the left and right pair for min_sum min_l = l min_r = n - 1 # Array should have at least two elements*/ if(n < 2): print("Invalid Input", end = "") return # Sort the elements */ quickSort(arr, l, r) while(l < r): sum = arr[l] + arr[r] # If abs(sum) is less # then update the result items if(abs(sum) < abs(min_sum)): min_sum = sum min_l = l min_r = r if(sum < 0): l += 1 else: r -= 1 print("The two elements whose sum is minimum are", arr[min_l], "and", arr[min_r])# Driver Codearr = [1, 60, -10, 70, -80, 85] n = len(arr)minAbsSumPair(arr, n)# This code is contributed by mohit kumar 29 |
C#
using System;class GFG{ static void minAbsSumPair(int []arr ,int n) { // Variables to keep track // of current sum and minimum sum int sum, min_sum = 999999; // left and right index variables int l = 0, r = n-1; // variable to keep track of the left // and right pair for min_sum int min_l = l, min_r = n-1; /* Array should have at least two elements*/ if (n < 2) { Console.Write("Invalid Input"); return; } /* Sort the elements */ sort(arr, l, r); while(l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if (Math.Abs(sum) < Math.Abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if (sum < 0) l++; else r--; } Console.Write(" The two elements whose " + "sum is minimum are " + arr[min_l]+ " and " + arr[min_r]); } // driver code public static void Main () { int []arr = {1, 60, -10, 70, -80, 85}; int n = arr.Length; minAbsSumPair(arr, n); } /* Functions for QuickSort */ /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ static int partition(int []arr, int low, int high) { int pivot = arr[high]; int i = (low-1); // index of smaller element for (int j = low; j < high; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp1 = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp1; return i+1; } /* The main function that implements QuickSort() arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ static void sort(int []arr, int low, int high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ int pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort(arr, pi+1, high); } }}// This code is contributed by Sam007 |
Javascript
<script> function minAbsSumPair(arr,n) { // Variables to keep track of current sum and minimum sum let sum, min_sum = 999999; // left and right index variables let l = 0, r = n-1; // variable to keep track of the left and right pair for min_sum let min_l = l, min_r = n-1; /* Array should have at least two elements*/ if(n < 2) { document.write("Invalid Input"); return; } /* Sort the elements */ sort(arr, l, r); while(l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less then update the result items*/ if(Math.abs(sum) < Math.abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if(sum < 0) l++; else r--; } document.write(" The two elements whose "+ "sum is minimum are "+ arr[min_l]+ " and "+arr[min_r]); } /* Functions for QuickSort */ /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ function partition(arr,low,high) { let pivot = arr[high]; let i = (low-1); // index of smaller element for (let j=low; j<high; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) let temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } /* The main function that implements QuickSort() arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */ function sort(arr,low,high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ let pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort(arr, pi+1, high); } } // main function let arr=[1, 60, -10, 70, -80, 85]; let n = arr.length; minAbsSumPair(arr, n); // This code is contributed by unknown2108</script> |
Output:
The two elements whose sum is minimum are -80 and 85
Time Complexity: complexity to sort + complexity of finding the optimum pair = O(nlogn) + O(n) = O(nlogn)
Auxiliary Space: O(1)
STL implementation of Method-2:
Algorithm
1) Sort all the elements of the input array using their absolute values.
2) Check absolute sum of arr[i-1] and arr[i] if their absolute sum is less than min update min with their absolute value.
3) Use two variables to store the index of the elements.
Implementation:
C++
// C++ implementation using STL#include <bits/stdc++.h>using namespace std;// Modified to sort by absolute valuesbool compare(int x, int y){ return abs(x) < abs(y);}void findMinSum(int arr[], int n){ sort(arr, arr + n, compare); int min = INT_MAX, x, y; for (int i = 1; i < n; i++) { // Absolute value shows how close it is to zero if (abs(arr[i - 1] + arr[i]) <= min) { // if found an even close value // update min and store the index min = abs(arr[i - 1] + arr[i]); x = i - 1; y = i; } } cout << "The two elements whose sum is minimum are " << arr[x] << " and " << arr[y];}// Driver codeint main(){ int arr[] = { 1, 60, -10, 70, -80, 85 }; int n = sizeof(arr) / sizeof(arr[0]); findMinSum(arr, n); return 0; // This code is contributed by ceeyesharish} |
Java
// Java implementation using STLimport java.io.*;class GFG{ static void findMinSum(int[] arr, int n){ for(int i = 1; i < n; i++) { if (!(Math.abs(arr[i - 1]) < Math.abs(arr[i]))) { int temp = arr[i - 1]; arr[i - 1] = arr[i]; arr[i] = temp; } } int min = Integer.MAX_VALUE; int x = 0, y = 0; for(int i = 1; i < n; i++) { // Absolute value shows how close // it is to zero if (Math.abs(arr[i - 1] + arr[i]) <= min) { // If found an even close value // update min and store the index min = Math.abs(arr[i - 1] + arr[i]); x = i - 1; y = i; } } System.out.println("The two elements whose " + "sum is minimum are " + arr[x] + " and " + arr[y]);}// Driver codepublic static void main(String[] args){ int[] arr = { 1, 60, -10, 70, -80, 85 }; int n = arr.length; findMinSum(arr, n);}}// This code is contributed by rag2127 |
Python3
# Python3 implementation using STLimport sysdef findMinSum(arr, n): for i in range(1, n): # Modified to sort by absolute values if (not abs(arr[i - 1]) < abs(arr[i])): arr[i - 1], arr[i] = arr[i], arr[i - 1] Min = sys.maxsize x = 0 y = 0 for i in range(1, n): # Absolute value shows how # close it is to zero if (abs(arr[i - 1] + arr[i]) <= Min): # If found an even close value # update min and store the index Min = abs(arr[i - 1] + arr[i]) x = i - 1 y = i print("The two elements whose sum is minimum are", arr[x], "and", arr[y])# Driver code arr = [ 1, 60, -10, 70, -80, 85 ]n = len(arr)findMinSum(arr, n)# This code is contributed by avanitrachhadiya2155 |
C#
// C# implementation using STLusing System;class GFG{ static void findMinSum(int[] arr, int n){ for(int i = 1; i < n; i++) { if (!(Math.Abs(arr[i - 1]) < Math.Abs(arr[i]))) { int temp = arr[i - 1]; arr[i - 1] = arr[i]; arr[i] = temp; } } int min = Int32.MaxValue; int x = 0, y = 0; for(int i = 1; i < n; i++) { // Absolute value shows how close // it is to zero if (Math.Abs(arr[i - 1] + arr[i]) <= min) { // If found an even close value // update min and store the index min = Math.Abs(arr[i - 1] + arr[i]); x = i - 1; y = i; } } Console.WriteLine("The two elements whose " + "sum is minimum are " + arr[x] + " and " + arr[y]);}// Driver Codestatic void Main() { int[] arr = { 1, 60, -10, 70, -80, 85 }; int n = arr.Length; findMinSum(arr, n);}}// This code is contributed by divyesh072019 |
Javascript
<script>// Javascript implementation using STLfunction findMinSum(arr, n){ for(let i = 1; i < n; i++) { if (!(Math.abs(arr[i - 1]) < Math.abs(arr[i]))) { let temp = arr[i - 1]; arr[i - 1] = arr[i]; arr[i] = temp; } } let min = Number.MAX_VALUE; let x = 0, y = 0; for(let i = 1; i < n; i++) { // Absolute value shows how close // it is to zero if (Math.abs(arr[i - 1] + arr[i]) <= min) { // If found an even close value // update min and store the index min = Math.abs(arr[i - 1] + arr[i]); x = i - 1; y = i; } } document.write("The two elements whose " + "sum is minimum are " + arr[x] + " and " + arr[y]);}// Driver codelet arr = [ 1, 60, -10, 70, -80, 85 ];let n = arr.length; findMinSum(arr, n); // This code is contributed by suresh07 </script> |
Output:
The two elements whose sum is minimum are -80 and 85
Time Complexity: O(nlogn)
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
