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:
- We are firstly accessing the X and Y at the same time. Proved.
- 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | def solution(A): A.sort() # Sort A in non-decreasing order if A[0] >= 0: return A[0] + A[0] # All non-negative if A[-1] <= 0: return -A[-1] - A[-1] # All non-positive front, back = len(A)-1, 0 minAbs = A[-1] + A[-1] # Final result # Travel the array from both ends to some center point. # See following post for the proof of this method. # https://34.145.67.234/2014/solution-to-min-abs-sum-of-two-by-codility while back <= front: temp = abs(A[back] + A[front]) # Update the result if needed if temp < minAbs: minAbs = temp # Adjust the pointer for next trying if back == front: break elif abs(A[back+1] + A[front]) <= temp: back += 1 elif abs(A[back] + A[front-1]) <= temp: front -= 1 else: back += 1; front -= 1 return minAbs |
you can just compare the sum A[i] + A[j] with 0.
Perfect! You are right!
May I post another solution using ruby:
More than welcome! 🙂
This was my solution which passed all testcases
(Just find the closest sum to the half sum)
We can stop when it reaches 0:
Exactly. Thanks for pointing it out.
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.
Here is my Python solution, with the comments.
The solution is really good, just one minor issue, with back+1.
It will give out of index error with this: [-4,-3,1]
Thanks for the catch! I’ve updated the solution.