Min Abs Sum task from codility-CodePudding

There is already a topic about this task, but I'd like to ask about my specific approach. The task is:

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

The abs sum of two for a pair of indices (P, Q) is the absolute value |A[P] A[Q]|, for 0 ≤ P ≤ Q < N.

For example, the following array A:

A[0] = 1 A1 = 4 A[2] = -3 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] A1 = |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 A1 A1 = |4 4| = 8. The abs sum of two for the pair (1, 2) is A1 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 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:

A[0] = 1 A1 = 4 A[2] = -3 the function should return 1, as explained above.

Given array A:

A[0] = -8 A1 = 4 A[2] = 5 A[3] =-10 A[4] = 3 the function should return |(−8) 5| = 3.

Write an efficient algorithm for the following assumptions:

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].

The official solution is O(N*M^2), but I think it could be solved in O(N). My approach is to first get rid of duplicates and sort the array. Then we check both ends and sompare the abs sum moving the ends by one towards each other. We try to move the left end, the right one or both. If this doesn't improve the result, our sum is the lowest. My code is:

def solution(A):
    A = list(set(A))
    n = len(A)
    A.sort()
    beg = 0
    end = n - 1
    min_sum = abs(A[beg]   A[end])
    while True:
        min_left = abs(A[beg 1]   A[end]) if beg 1 < n else float('inf')
        min_right = abs(A[beg]   A[end-1]) if end-1 >= 0 else float('inf')
        min_both = abs(A[beg 1]   A[end-1]) if beg 1 < n and end-1 >= 0 else float('inf')
        min_all = min([min_left, min_right, min_both])
        if min_sum <= min_all:
            return min_sum
        if min_left == min_all:
            beg  = 1
            min_sum = min_left
        elif min_right == min_all:
            end -= 1
            min_sum = min_right
        else:
            beg  = 1
            end -= 1
            min_sum = min_both

It passes almost all of the tests, but not all. Is there some bug in my code or the approach is wrong?

EDIT: After the aka.nice answer I was able to fix the code. It scores 100% now.

def solution(A):
    A = list(set(A))
    n = len(A)
    A.sort()
    beg = 0
    end = n - 1
    min_sum = abs(A[beg]   A[end])
    while beg <= end:
        min_left = abs(A[beg 1]   A[end]) if beg 1 < n else float('inf')
        min_right = abs(A[beg]   A[end-1]) if end-1 >= 0 else float('inf')
        min_all = min(min_left, min_right)
        if min_all < min_sum:
            min_sum = min_all
        if min_left <= min_all: 
            beg  = 1
        else:
            end -= 1

    return min_sum

CodePudding user response：

Just take this example for array A

-11 -5 -2 5 6 8 12

and execute your algorithm step by step, you get a premature return:

beg=0
end=6
min_sum=1
min_left=7
min_right=3
min_both=3
min_all=3
return min_sum

though there is a better solution abs(5-5)=0.

Hint: you should check the sign of A[beg] and A[end] to decide whether to continue or exit the loop. What to do if both >= 0, if both <= 0, else ?

Note that A.sort() has a non neglectable cost, likely O(N*log(N)), it will dominate the cost of the solution you exhibit.

By the way, what is M in the official cost O(N*M^2)?

And the link you provide is another problem (sum all the elements of A or their opposite).