Two Sum Zero

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.

Approach : Using the approach given in the 2 Sum post.

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 72 73 74 75 76 77 78 79 80 81 82 83 84

#include <iostream> #include <cmath> using namespace std; void mergeSort(int *, int, int); void merger(int *, int, int, int); void sumToZero(int *, int); void sumToZero(int *arr, int n){ int i = 0, j = n - 1, sum, minSum, minLeft, minRight; minSum = 999999; minLeft = i; minRight = j; while(i < j){ sum = arr[i] + arr[j]; if(abs(sum) > abs(minSum)){ minSum = sum; minLeft = i; minRight = j; } if(sum < 0){ i++; } else{ j--; } } cout << "Elements whose sum is close to 0 : " << arr[minLeft] << " " << arr[minRight]; cout << endl; } void mergeSort(int *arr, int low, int high){ int mid; if(low < high){ mid = (low + high)/2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); merger(arr, low, mid, high); } } void merger(int *arr, int low, int mid, int high){ int n1 = mid - low + 1; int n2 = high - mid; int left[n1], right[n2]; int i, j, k; i = 0; while(i < n1){ left[i] = arr[i + low]; i++; } i = 0; while(i < n2){ right[i] = arr[i + mid + 1]; i++; } i = 0; j = 0; k = low; while(i < n1 && j < n2){ if(left[i] <= right[j]){ arr[k++] = left[i++]; } else{ arr[k++] = right[j++]; } } while(i < n1){ arr[k++] = left[i++]; } while(j < n2){ arr[k++] = right[j++]; } } int main(){ int arr[] = {1, 60, -10, 70, -80, 85}; int n = sizeof(arr)/sizeof(arr[0]); mergeSort(arr, 0, n - 1); for(int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; sumToZero(arr, n); return 0; }