Sharing an answer code of mine about MinAbsSumOfTwo problem of Codility lesson 15.

# Lesson 15: MinAbsSumOfTwo

Let A be a non-empty zero-indexed array consisting of N integers.

The abs sum of two for a pair of indices $(P, Q)$ is the absolute value $\mid A[P] + A[Q]\mid$, for $% $.

For example, the following array A:

has pairs of indices (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2).
The abs sum of two for the pair (0, 0) is A[0] + A[0] = |1 + 1| = 2.
The abs sum of two for the pair (0, 1) is A[0] + A[1] = |1 + 4| = 5.
The abs sum of two for the pair (0, 2) is A[0] + A[2] = |1 + (−3)| = 2.
The abs sum of two for the pair (1, 1) is A[1] + A[1] = |4 + 4| = 8.
The abs sum of two for the pair (1, 2) is A[1] + A[2] = |4 + (−3)| = 1.
The abs sum of two for the pair (2, 2) is A[2] + A[2] = |(−3) + (−3)| = 6.

Write a function:

def solution(A)


that, given a non-empty zero-indexed array A consisting of N integers, returns the minimal abs sum of two for any pair of indices in this array.

For example, given the following array A:

the function should return 1, as explained above.

Given array A:

the function should return $\mid (−8) + 5\mid = 3$.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

# Answer Code in Python 3

• Time complexity: $O(N\log(N))$
• Space complexity: $O(N)$
# Python 3.6, Time complexity: O(nlog(n))
def solution(A):
# Exception for only one element in the list A
if len(A) == 1:
return abs(A[0]+A[0])

A.sort() # Sort the list

# Seperate list A into two lists
minus, plus = [], []
for i in range(len(A)):
if A[i]<0:
minus.append(A[i])
else:
plus.append(A[i])
minus.reverse()

# Exceptions
if len(minus) == 0: # there is no minus sign
return A[0]+A[0]
if len(plus) == 0: # there is no plus sign
return abs(A[-1]+A[-1])

min_ = min(abs(minus[0]+minus[0]), plus[0]+plus[0]) # Initial min_
right = 0
# Compare plus and minus lists
for i in range(len(plus)):
while right < len(minus):
if right-1 < 0 and right+1 < len(minus):
right += 1
continue
elif abs(plus[i]+minus[right-1])>=abs(plus[i]+minus[right]) and right+1 < len(minus):
right += 1
else: # Stop when the min for 'i' is found
right -= 1
break

# Check if it is min for until now
if min_ > abs(plus[i]+minus[right]):
min_ = abs(plus[i]+minus[right])

return min_


Tags:

Categories:

Updated: