# Codility ‘Tape Equilibrium’ Solution

##### Short Problem Definition:

Minimize the value |(A[0] + … + 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 = [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.

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

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 :).

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 🙂

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); } ```

• Alper Aykac

public class Class1 {

public static void main(String[] args) {

int N = Integer.parseInt(args[0]);
int P = Integer.parseInt(args[1]);
System.out.println(“P=” + P);
System.out.println(“N=” + N);
int sum = 0;
int sum1 = 0;
int sum2 = 0;

// one big loop O(N)
for (int t = 0; t P – 1 ? -1 * t : t;
}

//math
double f = (P – 1) * P / 2;
double f2 = N * (N + 1) / 2;
double r = 2 * f – f2;

//sum and substract…
for (int t = P; t <= N; t++) {
sum1 += t;
}
for (int t = 0; t <= P – 1; t++) {
sum2 += t;
}
int result=sum2 – sum1;

System.out.println("sum=" + sum);
System.out.println("result="+result);
System.out.println("r=" + r);
}
}

• sandip

[Tested : 100% correctness / 100% performance]

//Problem:
//Minimize the value |(A[0] + … + A[P-1]) – (A[P] + … + A[N-1])|.
int solution1(vector &A) {
// write your code in C++14 (g++ 6.2.0)
size_t sz = A.size();
if(sz == 0) return 0;
if(sz == 1) return A[0];

long sum = 0;
for(size_t i = 0; i < sz; i++)
{
sum += A[i];
}

long minVal=0;
long diffVal;
long leftSum = 0;
for(size_t i = 0; i < sz-1; i++)
{
leftSum += A[i];
diffVal = abs(leftSum-(sum-leftSum));
if(i==0)
minVal = diffVal;
else if( diffVal < minVal )
minVal = diffVal ;
}
return minVal;
}

• Alper Aykac

%100 performance and correctness in java…

public int solution(int[] A) {

IntStream intA = Arrays.stream(A);
int curDif = 0, minDif = 2147483647;
int lenght = A.length, sum = 0, sum2 = 0,idx = 0;

sum = intA.sum();
intA = Arrays.stream(A);
PrimitiveIterator.OfInt iter = intA.iterator();

while (iter.hasNext()) {
if ((idx +=1) == lenght)
break;
int i = iter.next();
sum2 += i;
curDif = Math.abs(sum2 – (sum – sum2));
minDif = curDif <= minDif ? curDif : minDif;
}
return minDif;
}

• Thomas

My code in C# 100% working.

class Solution {
public int solution(int[] a) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int i;
int r = 0;
int c = 0;
int leftsum;
int rightsum;
int absdiff;
int totalSum = a.Sum();
int[] b = new int[a.Length – 1];

for (i = 0; i < a.Length – 1; i++)
{
c = c + a[i];
leftsum = c;
rightsum = totalSum – leftsum;
absdiff = Math.Abs(leftsum – rightsum);
b[i] = absdiff;
}
r = b.Min();
return r;
}
}