Objective: Given an array of positive and negative integers, write a algorithm to find the two elements such their sum is closest to zero.
Example:
int a [] = {1, 4, -5, 3, -2, 10, -6, 20}; Output: Sum close to zero in the given array is : 1 int a [] = {-5, 5, 8}; Output: Sum close to zero in the given array is : 0 int a [] = {5, 8}; Output: Sum close to zero in the given array is : 13 int a [] = {-5,-5,-8}; Sum close to zero in the given array is : -10
Approach:
Naive approach: Use 2 loops. For each element in the array, find the sum with every other element and keep track of the minimum sum found.
Time Complexity : O(n^2) Space Complexity: O(1)
Sorting approach:
- Sort the array.
- This will bring all the negative elements at the front and positive elements at the end of the array.
- Track 2 numbers, one positive number close to 0, let’s call it as positiveClose and one negative number close to 0, let’s call it as negativeClose.
- take 2 pointers, one from the beginning of the array and another one from the end of the array. say pointers are i and j.
- Add A[i] + A[j], if sum > 0 then reduce j, j– and if sum < 0 then increase i ++.
- If sum > 0 compare it with positiveClose, if positiveClose>sum, do positiveClose = sum.
- If sum < 0 compare it with negativeClose, if negativeClose<sum, do negativeClose = sum.
- Repeat the step 5, 6, 7 till i<j.
- Return the minimum of absolute values of positiveClose and negativeClose, this will be the answer.
- At any point if sum = 0 then return 0 since this will be the closest to the 0 is possible.
- We can easily modify the code given below to track the two indexes as well for which the closest sum is possible.
Time Complexity : O(nlogn) Space Complexity: O(n) by using merge sort.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
public class SumCloseToZero { | |
public int findSum(int [] a){ | |
Arrays.sort(a); | |
int i=0; | |
int j = a.length–1; | |
int positiveClose = Integer.MAX_VALUE; | |
int negativeClose = Integer.MIN_VALUE; | |
while(i<j){ | |
int temp = a[i] + a[j]; | |
//check if temp is greater than 0 | |
if(temp>0){ | |
//check if positiveClose needs to be updated | |
if(positiveClose>temp){ | |
positiveClose = temp; | |
} | |
//decrement j, in order to reduce the difference, close to 0 | |
j—; | |
}else if(temp<0){ | |
//check if negative needs to be updated | |
if(negativeClose<temp){ | |
negativeClose = temp; | |
} | |
//increment i, in order to reduce the difference, close to 0 | |
i++; | |
}else{ | |
//means temp is 0, that is the closest to zero we can get, return 0 | |
return 0; | |
} | |
} | |
//check the least absolute value in postiveClose and negativeClose | |
return Math.min(Math.abs(positiveClose), Math.abs(negativeClose)); | |
} | |
public static void main(String[] args) { | |
int a [] = {1, 4, –5, 3, –2, 10, –6, 20}; | |
int closestSum = new SumCloseToZero().findSum(a); | |
System.out.println("Sum close to zero in the given array is : " + closestSum); | |
} | |
} | |
Output: Sum close to zero in the given array is : 1