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, A, ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of:
|(A + A + ... + 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 = 3 A = 1 A = 2 A = 4 A = 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:
that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
For example, given:
A = 3 A = 1 A = 2 A = 4 A = 3
the function should return 1, as explained above.
N is an integer within the range
[2..100,000]; each element of array A is an integer within the range
- 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.