2.7K
Question: Given an array with both positive and negative numbers, find the two elements such that their sum is closest to zero. ?
Input: arr [] = {1, 60, -10, 70, -80, 85}
Output: -80, 85 (Their sum is -5 that is closest to 0(zero))
What we discussed was the most naive approach by using two for loops. However, this method is not optimized and will take a lot of time if the data is very large. We need to improve the complexity of the program.
One such method is discussed below.
- Sort all the elements of the given input array.
- Maintain two indexes one at the beginning (i=0) and one at the end (j=n-1). Also maintain two variables to keep track of smallest positive sum closest to zero and smallest negative sum closest to zero.
- While (i<j)
->If the current pair sum > zero and < positiveClosest, then update the positiveClosest. Decrement j;
->If the current pair sum < zero and > negativeClosest, then update the negativeClosest. Increment i.
->Else print the pair.
Here is an implementation of the above algorithm.
int twoElementsWithMinSum(int arr[],int size) { //starting index and last index int i=0, j=n-1; int temp,; //set the positiveClosest and negativeClosest to //maximum and minimum integer values int positiveClosest = INT_MAX; int negativeClosest = INT_MIN; //to store the pair of numbers int p1=0,p2=0; int n1=0,n2=0; //sort the array quickSort(arr,size); //loop between start index and last index while(i<j) { //sum the pair temp = arr[i] + arr[j]; //check for positive sum if(temp>0) { if(temp < positiveClosest) positiveClosest = temp; p1=arr[i]; p2=arr[j]; //decrement last index j--; } //check for negative sum else if(temp<0) { if(temp > negativeClosest) negativeClosest = temp; n1=arr[i]; n2=arr[j]; //increment first index i++; } else { printf("The Closest sum is by numbers = %d",(arr[i]+arr[j])); return; } } if((negativeClosest*-1)<positiveClosest) printf("%d %d",n1,n2); else printf("%d %d",p1,p2); } Time Complexity:- O(n*log(n)), for sorting the array
Space Complexity:- O(1)
