# Codility ‘MinAbsSumOfTwo’ Solution

##### Short Problem Definition:

Find the minimal absolute value of a sum of two elements.

MinAbsSumOfTwo

##### Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(1)

##### Execution:

Using the caterpillar method on a sorted list.

##### Solution:

C-style python

```def solution(A):
value = 2000000000
front_ptr = 0
back_ptr = len(A)-1
A.sort()

while front_ptr <= back_ptr: value = min(value, abs(A[front_ptr] + A[back_ptr])) if abs(A[front_ptr]) > abs(A[back_ptr]):
front_ptr += 1
else:
back_ptr -= 1

return value
```

Functional pythonesque:

```from itertools import *
def getAbsDiff(t):
return abs(t[0] + t[1])

def solution(A):
A.sort(key=abs)
return getAbsDiff(min(chain(izip(A, A),izip(A,A[1:])), key = getAbsDiff))
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

• Mikhail Manukhin

Martin,
Thank you for this wonderful solution! I like it because it covers all cases with such short code. However, I think it makes sense to process two special cases separately – when all elements are non-negative and all elements are non-positive.

• Well, in the search space of all possible combinations, the case with all + or all – numbers is very unlikely. You would have to add additional code to check whether this condition holds and potentially skip the sort. Yet you introduce more complexity to test and for other developers to understand.
Do you have a specific reason you consider those cases special?

• Mikhail Manukhin

The only reason is performance benefit – it will give immediate answer for these cases.

• Yixuan Eric Wang

Hey, Martin
A = sorted(A,key=abs) seems more pythonic, sorting A by the absolute value, then add the neighboring pairs to find the minimum. Well, it lost the essence of caterpillar

https://codility.com/demo/results/trainingRU4HQN-S6J/

• Jurek Tworkowski

Watch and learn people ðŸ˜‰ 100%

public int solution(int[] A) {
// write your code in Java SE 8
int N = A.length;

if (N == 1)
return Math.abs(A[0] * 2);
java.util.Arrays.sort(A);

if(A[0] >= 0 && A[N-1] >= 0) // all positive
return (int) Math.abs((long) A[0] * 2);
if(A[0] <= 0 && A[N-1] <= 0) // all negative
return (int) Math.abs((long) A[N-1] * 2);

long currAbsSum = 0;
long minAbsSum = Long.MAX_VALUE;

for (int i = 0; i = i) {

currAbsSum = Math.abs((long) A[i] + (long) A[j]);
if(currAbsSum == 0)
return 0;
minAbsSum = Math.min(currAbsSum, minAbsSum);

if (Math.abs(A[i]) >= Math.abs(A[j]))
i++;
else
j–;
}
if(A[i] > 0) break;
}

return (int) minAbsSum;
}