Codility ‘MinAbsSumOfTwo’ Solution

Short Problem Definition:

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

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • 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;
    }