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