Table of Contents
If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
Problem :
Given array of +ve and -ve integers ,we need to find a pair whose sum is closed to Zero in Array.
For example:
|
1 2 3 4 |
array[]={1,3,-5,7,8,20,-40,6}; The pair whose sum is closest to zero : -5 and 6 |
Solution :
Solution 1:
You can check each and every pair of numbers and find minimum sum.
Java code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public static void findPairWithMinSumBruteForce(int arr[]) { if(arr.length<2) return; // Suppose 1st two element has minimum sum int minimumSum=arr[0]+arr[1]; int pair1stIndex=0; int pair2ndIndex=1; for (int i = 0; i < arr.length; i++) { for (int j = i+1; j < arr.length; j++) { int tempSum=arr[i]+arr[j]; if(Math.abs(tempSum) < Math.abs(minimumSum)) { pair1stIndex=i; pair2ndIndex=j; minimumSum=tempSum; } } } System.out.println(" The pair whose sum is closest to zero : "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]); } |
Solution 2:
- Sort the array.
- We will maintain two indexes one at beginning (l=0) and one at end (r=n-1)
- iterate until l < r
- Calculate sum of arr[l] + arr[r]
- if abs (sum) < abs (minSum), then update the minimum sum and pair.
- If sum is less than 0, this means if we want to find sum close to 0, do r–
- If sum is greater than 0,this means if we want to find sum close to 0 , do l++
Java code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
public static void findPairWithMinSum(int arr[]) { // Sort the array, you can use any sorting algorithm to sort it Arrays.sort(arr); int sum=0; int minimumSum = Integer.MAX_VALUE; int n=arr.length; if(n<0) return; // left and right index variables int l = 0, r = n-1; // variables to keep track of the left and right index pair for minimumSum int minLeft = l, minRight = n-1; while(l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less than min sum, we need to update sum and pair */ if(Math.abs(sum) < Math.abs(minimumSum)) { minimumSum = sum; minLeft = l; minRight = r; } if(sum < 0) l++; else r--; } System.out.println(" The pair whose sum is minimun : "+arr[minLeft]+" "+ arr[minRight]); } |
Time complexity : O(NLogN)
Java program to find a pair whose sum is closest to zero:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
package org.arpit.java2blog; import java.util.Arrays; public class findPairClosestToZero { public static void main(String[] args) { int array[]={1,30,-5,70,-8,20,-40,60}; findPairWithMinSumBruteForce(array); findPairWithMinSum(array); } public static void findPairWithMinSumBruteForce(int arr[]) { if(arr.length<2) return; // Suppose 1st two element has minimum sum int minimumSum=arr[0]+arr[1]; int pair1stIndex=0; int pair2ndIndex=1; for (int i = 0; i < arr.length; i++) { for (int j = i+1; j < arr.length; j++) { int tempSum=arr[i]+arr[j]; if(Math.abs(tempSum) < Math.abs(minimumSum)) { pair1stIndex=i; pair2ndIndex=j; minimumSum=tempSum; } } } System.out.println(" The pair whose sum is closest to zero using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]); } public static void findPairWithMinSum(int arr[]) { // Sort the array, you can use any sorting algorithm to sort it Arrays.sort(arr); int sum=0; int minimumSum = Integer.MAX_VALUE; int n=arr.length; if(n<0) return; // left and right index variables int l = 0, r = n-1; // variables to keep track of the left and right index pair for minimumSum int minLeft = l, minRight = n-1; while(l < r) { sum = arr[l] + arr[r]; /*If abs(sum) is less than min sum, we need to update sum and pair */ if(Math.abs(sum) < Math.abs(minimumSum)) { minimumSum = sum; minLeft = l; minRight = r; } if(sum < 0) l++; else r--; } System.out.println(" The pair whose sum is minimun : "+arr[minLeft]+" "+ arr[minRight]); } } |
|
1 2 3 4 |
The pair whose sum is closest to zero using brute force method: 1 -5 The pair whose sum is closest to zero : -5 1 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
