# Solution to Min-Abs-Sum-Of-Two by codility

21 Apr

Question Name: Min-Abs-Sum-Of-Two or MinAbsSumOfTwo

There are two O(nlogn) solutions for this question. Both solutions have the same overall time complexity and space complexity. And both solutions need to sort the array in non-decreasing order first.

The first solution would sort the array with O(nlogn). Then for each element X in array, we could use binary search O(logn) to find the closest element Y to –X, so that |X+Y| is the closest to 0 (similar with the problem 3Sum-closest). To try all N elements, we need O(nlogn) to get N result as |X+Y|. Finally, linear time is needed to find the minimal one |X+Y|, which could be done while trying each round. Totally the time complexity is O(nlogn).

The second solution sorts the array with O(nlogn). We set two pointers (X and Y) to each end, and move the pointers from outside to inside by one or zero step in each round until them meet. The final result must be one of X and Y combination. Since each element in the sorted array will be accessed one and only one time, the time complexity is O(n). Totally the time complexity is O(nlogn). We will prove that, we definitely will meet the right X and Y combination in our method.

Without loss of generality, we consider X and Y are two different elements. ASSUME the array A is already SORTED, and the RIGHT ANSWER is in the position X and Y like:

————X————Y—————-

We are accessing the elements once and only once. So there are two cases:

1. We are firstly accessing the X and Y at the same time. Proved.
2. We are firstly accessing the X and Y at different time. Without loss of generality, we access X firstly.
——————————————————
a. If A[X] + A[Y] >=0: the array is sorted , so for all i > Y, we have
A[X] + A[i] >= A[X] + A[i-1] >= 0.
=> A[X] + A[-1] >= A[X] + A[-2] >= … >= A[X] + A[Y+1] >= A[X] + A[Y] >=0
=> |A[X] + A[-1]| >= |A[X] + A[-2]| >= … >= |A[X] + A[Y+1]| >= |A[X] + A[Y]| >=0.
So our algorithm will guide us to move from any position after Y to Y finally.
——————————————————
b. If A[X] + A[Y] < 0: let a = |A[X] + A[Y]|, A[X] + A[Y+1] >= A[X] + A[Y] = -a with sorted array:
If A[X] + A[Y+1] == -a or a, switch to prove with answer positions (X, Y+1);
If A[X] + A[Y+1] is in range (-a, a), then |A[X] + A[Y+1]| < a = |A[X] + A[Y]|. It is contradict with the assumption |A[X] + A[Y]| is the minimal. Thus this case is not possible.
If A[X] + A[Y+1] > a > 0, prove with the steps in 2.a.

End of proof.

### 12 Replies to “Solution to Min-Abs-Sum-Of-Two by codility”

1. Vadim says:

you can just compare the sum A[i] + A[j] with 0.

• Sheng says:

Perfect! You are right!

2. Botond Orban says:

May I post another solution using ruby:

• Sheng says:

More than welcome! 🙂

3. Shadi Al Barhouch says:

This was my solution which passed all testcases
(Just find the closest sum to the half sum)

4. Newman says:

We can stop when it reaches 0:

• Sheng says:

Exactly. Thanks for pointing it out.

5. Miguel says:

Hey guys, I had tried a similar approach but it kept failing on one of my test cases. Then I implemented what you propose but it continues to fail.
This is the test case: 11, -8, 4, 5, 0, -10, 3
sorted:
-10, -8, 0, 3, 4, 5, 11
So on the first run it will do abs(11-10) = 1
on the rest of the runs of the loop, it will continue to move both edges and actually never do 0+0. So it returns 1 as the solution when actually the min abs sum is 0+0 = 0.
Has anyone run into this scenario?
This is my code on C#

• Sheng says:

I felt bad that you did not read my proof 🙁 Anyway, to get the right solution, you could change the line #11 and #13 by replacing minAbsSum with currentSum.

6. Ana says:

Here is my Python solution, with the comments.

7. JASON LEE says:

The solution is really good, just one minor issue, with back+1.
It will give out of index error with this: [-4,-3,1]

• Sheng says:

Thanks for the catch! I’ve updated the solution.