# Codility 'Tape Equilibrium' Solution

Martin Kysel · July 22, 2014

##### Short Problem Definition:

Minimize the value (A + … + A[P-1]) - (A[P] + … + A[N-1]).

TapeEquilibrium

##### Complexity:

expected worst-case time complexity is `O(N)`

expected worst-case space complexity is `O(N)`

##### Execution:

In the first run I compute the left part up to the point i and the overall sum last. Then I compute the minimal difference between 0..i and i+1..n.

##### Solution:
``````
import sys

def solution(A):
#1st pass
parts =  * len(A)
parts = A

for idx in xrange(1, len(A)):
parts[idx] = A[idx] + parts[idx-1]

#2nd pass
solution = sys.maxint
for idx in xrange(0, len(parts)-1):
solution = min(solution,abs(parts[-1] - 2 * parts[idx]));

return solution
``````

``````
#include <algorithm>
#include <climits>

int solution(vector<int> &A) {
unsigned int size = A.size();

vector<long long> parts;
parts.reserve(size+1);

long long last = 0;

for (unsigned int i=0; i<size-1; i++){
if (i == 0){
parts.push_back(A[i]);
} else {
parts.push_back(A[i]+parts[i-1]);
}
if (i==size-2){
last = parts[i]+ A[i+1];
}
}

long long solution = LLONG_MAX;

for(unsigned int i=0; i<parts.size(); i++){
solution = min(solution,abs(last - 2 * parts[i]));
}

return solution;
}
``````