TapeEquilibrium - Python

Question

I'm studying through Codility and I'm doing this lesson.

So the basically solution that I thought at first time was:

#SOLUTION 1
def solution(A):

    diff = []
    for x in range(1,len(A)):
        first_half = sum(A[:x])
        second_half = sum(A[x:])
        diff.append(abs(first_half - second_half))
    return min(diff)

I scored 100% in 'Correctless' but 0% in 'Performance'.

So I thought that maybe my problem was something with diff.append inside my loop.

Then I tried to use a List Comprehension like that:

#SOLUTION 2
def solution(A):

    result = min((abs(sum(A[:x]) - sum(A[x:])) for x in range(1,len(A))))
    return result

I also tried to remove min() and abs() from my loop, so I tried use pure math:

#SOLUTION 3
def solution(A):

result = [sum(A[:x]) - sum(A[x:]) if (sum(A[:x]) - sum(A[x:])) > 0 else sum(A[:x])*-1 - sum(A[x:])*-1 for x in range(1,len(A))]
return abs(min(result))

But again, I received a 0% of performance. All the solutions has a O(N * N).

So probably my problem is in use sum( ) inside a loop... what is the best way to improve the performance of my code?

PS: This is not a duplicated question, the problem it's the same of others questions about that Lesson on Codility, but my solution it's different. And I also prefer to use pure Python for that solution, if possible.

Answer 1

You could try this approach to see if you got some improvements in performance? (Just test it and all passed with flying colors as well)

This should be just O(n) as we move along the list with each loop indexing the head and tail.

def solution(A):
    heads = A[0]
    tails = sum(A[1:])

    diff = abs(heads - tails)

    for index in range(1, len(A)-1):
        heads += A[index]
        tails -= A[index]
        if abs(heads -tails) < diff:
            diff = abs(heads - tails)
    return diff