Codility ‘Tape Equilibrium’ Solution

Short Problem Definition:

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

Link

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 = [0] * len(A)
    parts[0] = A[0]
 
    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;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin