TapeEquilibrium Codility implementation not achieving 100%

Question

Given the following task description from here :

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7 
P = 2, difference = |4 − 9| = 5 
P = 3, difference = |6 − 7| = 1 
P = 4, difference = |10 − 3| = 7

Write a function:

def solution(A)

that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.

For example, given:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

the function should return 1, as explained above.

Assume that:

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

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

Elements of input arrays can be modified.

I decided to implement an algorithm that with 2 counters/pointers (one from leftmost and another one from rightmost of the array input) representing the total sum of values that the pointer(s) have traversed. The process works by first deciding which pointer to move closer to the other in each iteration, which is looking the next element directly next to the location of the current pointer, attempt to temporarily sum the value to the pointer, and then find the absolute difference between the other pointer. The absolute difference is also calculated for the other pointer, and then compared against each other's pointer temporarily accumulated value, to find out which one yields lower absolute difference. The pointer move that yields the lowest absolute difference then performs the actual summation to the pointer, and that particular pointer moves for that iteration.

The following is my code :

from math import fabs

def solution(A):
    l_ptr = 0
    r_ptr = A.__len__() - 1
    l_sum = A[l_ptr]
    r_sum = A[r_ptr]
    while l_ptr < r_ptr - 1:
        if fabs(l_sum + A[l_ptr + 1] - r_sum) > fabs(l_sum - (r_sum + A[r_ptr - 1])):
            r_ptr -= 1
            r_sum += A[r_ptr]
        else:
            l_ptr += 1
            l_sum += A[l_ptr]
    return (int)(fabs(l_sum - r_sum))

In the test case, I didn't manage to achieve 100% test accuracy, and I'm not sure exactly why, but I think perhaps it has something to do with the pointer not being able to look for the array element that are several steps away at a given iteration and the possibility of having negative value. The followings are the test cases that it fails on according to Codility :

▶ small_random 
random small, length = 100 ✘WRONG ANSWER 
got 269 expected 39
▶ large_ones 
large sequence, numbers from -1 to 1, length = ~100,000 ✘WRONG ANSWER 
got 228 expected 0
▶ large_random 
random large, length = ~100,000 ✘WRONG ANSWER 
got 202635 expected 1

Obviously provided that it's evaluation of a test set, the actual input data for the test are not given, so it's more difficult for me to figure out what part of my algorithm that is incorrect and the causes. Could someone provide an explanation (preferably with a sample input data) what I misunderstood and the cause? Thank you in advance.

Answer 1

Algorithm

Your algorithm works for input with only positive integers. But it may not work with some input that contains negative numbers, for example it gives incorrect result for:

[-1, 1, 1, -1, -2]

Why does it work for all positive numbers?

At any point in your loop, you basically have:

• leftsum: the sum of elements on the left so far
• leftnext: the next element on the left
• rightsum: the sum of elements on the right so far
• rightnext: the next element on the right

When you know that all remaining elements in the middle are non-negative, then you can safely decide whether to take the left or the right, by minimizing the difference between leftsum + leftnext and rightsum + rightnext. This is safe, because all the remaining elements are non-negative, therefore the difference can only shrink, or otherwise be minimal.

But when there can be negative numbers in the middle, you don't have such knowledge, and it can be impossible to decide which side to advance.

Consider this alternative that's simple and intuitively easy to understand, and it's guaranteed to give correct result:

• Set left to the first element
• Set right to the total sum - left
• Initialize mindiff to the absolute difference of left and right
• Iterate from the 2nd element until the -1th: add to left and subtract from right and update mindiff (A quick tip for writing the loop: for value in A[1:-1]: ...)
• return mindiff

Technique

It's strange you did from math import fabs when you don't need floating point math to solve this problem. You can use abs instead of fabs.

Instead of A.__len__() it's more natural to use len(A).

Answer 2

According to @janos answer here is a possible implementation in python:

def solution(A):
    if len(A) == 1:
        return 0

    if len(A) == 2:
        return abs(A[0] - A[1])

    left = A[0]
    right = sum(A) - left
    min_difference = abs(left-right)

    for value in A[1:-1]:
        left += value
        right -= value
        if abs(left - right) < min_difference:
            min_difference = abs(left - right)

    return min_difference

The problem occurs when the array shifted left sum difference (l_sum + A[l_ptr + 1] - r_sum) and shifted right sum difference (l_sum - (r_sum + A[r_ptr - 1]) are equal. Then you have to choose between incrementing the l_ptr or decrementing the r_ptr. In your case you increment the l_ptr, but you can not know whenever it was the good pointer to increment. It is possible that the r_ptr has to be decremented.

That's why we need the sum of the array in order to have prior knowledge about the array elements.