Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find two elements whose sum is closest to zero

Objec­tive: Given an array of pos­i­tive and neg­a­tive inte­gers, write a algo­rithm to find the two ele­ments such their sum is clos­est to zero.

Exam­ple:

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 ele­ment in the array, find the sum with every other ele­ment and keep track of the min­i­mum sum found.

Time Com­plex­ity : O(n^2) Space Com­plex­ity: O(1)

Sort­ing approach:

  1. Sort the array.
  2. This will bring all the neg­a­tive ele­ments at the front and pos­i­tive ele­ments at the end of the array.
  3. Track 2 num­bers, one pos­i­tive num­ber close to 0, let’s call it as pos­i­tive­Close  and one neg­a­tive num­ber close to 0, let’s call it as negativeClose.
  4. take 2 point­ers, one from the begin­ning of the array and another one from the end of the array. say point­ers are i and j.
  5. Add A[i] + A[j], if sum > 0 then reduce j, j– and if sum < 0 then increase i ++.
  6. If sum > 0 com­pare it with pos­i­tive­Close, if positiveClose>sum, do pos­i­tive­Close = sum.
  7. If sum < 0 com­pare it with neg­a­tive­Close, if negativeClose<sum, do neg­a­tive­Close = sum.
  8. Repeat the step 5, 6, 7 till i<j.
  9. Return the min­i­mum of absolute val­ues of pos­i­tive­Close and neg­a­tive­Close, this will be the answer.
  10. At any point if sum = 0 then return 0 since this will be the clos­est to the 0 is possible.
  11. We can eas­ily mod­ify the code given below to track the two indexes as well for which the clos­est sum is possible.

Time Com­plex­ity : O(nlogn) Space Com­plex­ity: O(n) by using merge sort.

Com­plete Code:

Output:
Sum close to zero in the given array is : 1

You may also like...