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

21 Apr

Question: https://codility.com/demo/take-sample-test/min_abs_sum_of_two

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.

9 thoughts on “Solution to Min-Abs-Sum-Of-Two by codility

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

  2. May I post another solution using ruby:

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

  4. We can stop when it reaches 0:

  5. 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#

    • 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.

Leave a Reply

Your email address will not be published. Required fields are marked *