Home > Applied Algorithms, Sorting > Find a pair (not consecutive) of numbers in an array whose sum is closest to zero.

Find a pair (not consecutive) of numbers in an array whose sum is closest to zero.

The problem statement is as defined in the title of the post. Please note that the problem is only interesting when the array has both negative and positive numbers and the numbers are randomly ordered. Now let me guide you through the whole thought process. (Don’t be a dumb person. The thought process is important even though the pseudo code is there at the end. Read through it.)

So tell me, how would you go forward in searching for two numbers (not necessarily consecutive) in an array of positive and negative numbers whose sum is closest to zero? What is the best possible algorithm that comes to your mind?

O(n^2) ? That is lame. Anyone can do that.

Optimized version of O(n^2)  but still O(n^2)? Now you are talking like a cornered person who can’t think of a way out.

Can’t you think up of an O(n lg n) algorithm? What was it that we studied in the last post? Sorting. And what is the time complexity of some of those algorithms? Right. You just made the connection and got the hint. (use Sorting algorithms)

You: Ok. So I sorted the array, but how does that help me. I still have the same old O(n^2) algorithm.

Me: Well, did I ask you to sort it in the old-fashioned way? How about a modified sort?

If you still haven’t figured it out, here it is plain and simple:

You sort the array neglecting the signs on the numbers. For example,

2 -1 6 -3 -4 3 11

becomes, -1 2 -3 3 -4 6 11

Now, can you figure it out? Well all you need to do is find the sum of each pair of consecutive elements of the array and find the pair that sums closest to zero (In this case, the sum of -3 and 3). You have your answer! 🙂

Pseudo Code :

-> Input array

-> Sort array neglecting sign of numbers

-> Sum up each pair of consecutive numbers in this new array

-> The pair with the sum closest to zero is your answer.

Why does this work? It works because you found out the elements that are closest to each other inspite of the signs. Thus, these are the potential pairs which will give the sum closest to zero.

The whole trick was in ignoring the signs and your sorting algorithm did the rest. That is a pretty good example of the application of sorting algorithms. One that is not so apparent but comes to your mind if you know your basics! Hope you took something good from this first applied algorithm post! 🙂

See you soon.

Advertisements
  1. Nikos Karamitrou
    December 1, 2014 at 12:06 am

    Actually the problem statement states that the pair of numbers need to be not consecutive. The pseudocode doesn’t do that check. It could be that “2 -1 6 -3 3 -4 11” is given which the algorithm is going to return back the (-3, 3) pair but -3 and 3 are consecutive numbers in the initial array. ?

    • December 5, 2014 at 10:42 am

      It says “need not be consecutive”. Which means that they may or may not be consecutive.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: