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
  • Anass

    Would someone explain please why he is multiplying by 2 (line 12 in python, line 26 in C)

    • Hi Anass, sorry for the late answer, I did not notice your post.

      You are to compute the difference between the left part and the right part. The parts vector contains the cumulative sum up to that point. The last entry is the sum of all parts. By substracting the parts[idx] once from the overall sum, you get the right part. To get the difference between the right and the left part, you subtract the left part again. Giving you 2* parts[idx].

      Cheers

  • Sergii Kozlov

    Can this be also a solution?

    # you can use print for debugging purposes, e.g.
    # print “this is a debug message”
    def solution(A):
    arr = []
    for val in range(1, len(A)):
    leftArr = A[:val]
    print leftArr
    rightArr = A[val:]
    print rightArr
    arr.append(abs(sum(leftArr) – sum(rightArr)))
    print arr
    arr.sort()
    return arr[0]

    • Hi,

      it does solve the problem but: the upper runtime O-notation for this problem is O(N), sorting your array requires O(NlogN) time. You might not pass the test suite.

  • Ernesto Cabrera

    Hi All,

    Thanks for your comments about the TapeEquilibrium problem.

    I implemented the following two solutions in codify https://codility.com/demo/results/demoR47NP2-Q5B/ (100%, 100%), https://codility.com/c/intro/demoZQHJBP-AJZ (83%, 91%).

    A nice thing about these solutions is that they don’t need an additional array to store the values. This might be important for large arrays. I’d love to here your comments about how to improve them further.

    Thanks,

    erncab

    public int GetMinimumAbsoluteDifferenceWithVariables(int[] A)
    {
    // write your code in C# 6.0 with .NET 4.5 (Mono)

    var length = A.Length;

    if (length == 1) return A[0];
    if (length == 2) return Math.Abs(A[0] – A[1]);

    var leftSum = 0;
    var rightSum = 0;

    for (var i = 0; i < length; i++)
    {
    rightSum += A[i];
    }

    var difference = int.MaxValue;

    for (var i = 0; i < length – 1; i++)
    {
    var value = A[i];

    leftSum += value;
    rightSum -= value;

    difference = Math.Min(difference, Math.Abs(rightSum – leftSum));

    if (difference == 0) return 0;
    }

    return difference;
    }

    • Hi Ernesto,

      nice solution. I did not realise that you can solve it with just two running values. But you are right, no need for a whole array.

      I prefer not to have multiple exit points from functions. If you really wish to optimise special cases and you found an ‘optimal solution’ break out of the cycle and return normally. As functions get bigger, it makes them more readable.

      Thanks for sharing with us!

  • Арсений Чеботарёв

    Just for collection: It’s my tightly packed (JS people say Uglified) C
    which avoids double counting (so no any long longs) and lowers space
    complexity to the bone. I use early returns and one-liners, cose they
    save braces and white space in such obvious cases. Result is all-greens
    as expected, actually greenest ever


    int solution(int A[], int N) {
    if (N==2) return abs(A[0]-A[1]);
    for (int i=1;i<N-1;i++) A[N-1]+=A[i];
    int diff = abs(A[0]-A[N-1]);
    for (int i=1;i<N-1;i++) {
    A[0]+=A[i]; A[N-1]-=A[i];
    if (abs(A[0]-A[N-1])<diff) diff=abs(A[0]-A[N-1]);
    }
    return diff;
    }

  • Арсений Чеботарёв

    Beads of Stone Solution. It’s very tight especially in regard of space.

    int solution(int A[], int N) {
    if (N==2) return abs(A[0]-A[1]);
    for (int i=1;i<N-1;i++) A[N-1]+=A[i];
    int diff = abs(A[0]-A[N-1]);
    for (int i=1;i<N-1;i++) {
    A[0]+=A[i]; A[N-1]-=A[i];
    if (abs(A[0]-A[N-1])<diff) diff=abs(A[0]-A[N-1]);
    }
    return diff;
    }

  • Nico
    • Ahmed Wahdan
      • I’ve looked at the code and it seems OK to me. There is no reason why it should be N*N. There are 2 separate loops… Also the logic seems to be absolutely correct…

        • Ahmed Wahdan

          I found that the index is the problem. It’s supposed to be int, but I declared it as char which lead to an infinite loop with N more than 255 because of overflow.

  • Sunovavic

    Is it faster to implement your own summation or use Linq? And is using Linq considered, cheating?
    public int TapeEquilibrium(int[] arr)
    {
    long left = arr[0];
    long right = arr.Skip(1).Sum();
    var min = (int)Math.Abs(left – right);
    for (var i = 1; i < arr.Length – 1; i++)
    {
    left += arr[i];
    right -= arr[i];
    var diff = (int) Math.Abs(left – right);
    if (diff < min) min = diff;
    }
    return min;
    }

    • I don’t have any experience with Linq. Would you mind to explain why it would help?

      • Sunovavic

        Linq provides a lot of additional functionality and shortens the code like for this instance, I just call the Sum() on an array instead of having implementing a for loop. It also provides sorting operations which I believe is using Quicksort so instead of writing a quicksort implementation, I can sort an array in a single line of code.

        • Hmm. Nice. The library looks pretty functional. Feels almost like Scala :).

          As for your question:
          Linq does not seem to implement any hardcore functionality that I personally would consider cheating. It is just syntactic sugar and some lambdas. Now, if you can just import cpplinq.hpp in the Codility environment, I guess it would be allowed. Copy-pasting the whole hpp file from github into the Codility editor sounds a bit crazy to me.

          Thanks for pointing out the library.

  • Yogendra

    C# code :

    using System;
    using System.Linq;

    class Solution {
    public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)

    Int64 _pRight = A[0];
    Int64 _sum = A.Sum();
    var _pLeft = _sum – _pRight;
    int _minNumber = Convert.ToInt32(Math.Abs(_pRight – _pLeft));
    for (int i = 1; i < A.Length; i++)
    {
    _pRight += A[i];
    _pLeft -= A[i];
    int _difference = Convert.ToInt32(Math.Abs(_pRight – _pLeft));

    if (_difference < _minNumber)
    {
    _minNumber = _difference;

    }

    }

    return _minNumber;
    }
    }

    • I am wondering. Is C# always using so many underscores :)?

    • Yogendra

      No, I just used for variable declaration 🙂

    • Adi

      Your solution would be perfect, But it is missing a -1 in the for loop definition. It should be “i < A.Length – 1"

  • Arun Kumar

    c#: Tested code

    public static int solution(int[] A)
    {
    int left = 0, right = 0, index = 0;
    bool flag=false;
    for (int i = 0; i < A.Length; i++)
    {
    left = 0;right = 0;
    for (int i1 = 0; i1 <= i; i1++)
    {
    left += A[i1];
    }

    for (int j1 = i + 2; j1 <= A.Length; j1++)
    {
    if (j1 < A.Length)
    {
    right += A[j1];
    }
    }
    if (left == right)
    {
    index = i + 1;
    flag = true;
    }

    }
    if (flag == false)
    { return -1; }
    else {
    return index;
    }
    }

  • Michiel van der Blonk
    • Mihai Raulea

      that is not one pass. note you init the head sum and tail sum, that counts as a pass. then, you go over the vector again to find the minimum.

  • Hamka

    (tested) PHP code:

    function solution($A) {
    // write your code in PHP5.5
    $sum=array_sum($A);
    $size=count($A);
    $temp=0;
    $arr_temp=array();
    for($i=0; $i<$size-1;$i++){
    if($i==0) $temp=$A[$i];
    else $temp+=$A[$i];
    $arr_temp[$i] = abs(($sum - $temp) - $temp);
    }
    return min($arr_temp);
    }