# TapeEquilibrium implementation

I took a test at Codility called TapeEquilibrium. The task description that I received can be seen here.

I came up with a solution that worked, and I was pretty happy with. However, the performance was apparently awful. The expected time complexity is apparently supposed to be $O(N)$, but I got $O(N * N)$. I'm not quite sure what exactly that means, but I've heard about it several times.

I'd like some help on improving my solution and get information about what I did wrong and how it could be done better, and why. I'm doing this to learn and improve.

public int solution(int[] A) {
int min = Int32.MaxValue;
for (int i = 0; i < A.Length - 1; i++) {
// p = i + 1
int part1 = 0, part2 = 0;
for (int j = 0; j <= i; j++) part1 += A[j];
for (int j = i + 1; j <= A.Length - 1; j++) part2 += A[j];

int val = Math.Abs(part1 - part2);
if (val < min) min = val;
}
return min;
}

• Hi! I removed the off topic part of your question. You might want to try asking that on Programmers, but I'm not 100% sure it's on topic there. Please be sure to visit their help center before posting there. Nov 24, 2014 at 14:52
• Nov 24, 2014 at 19:55

You have two unnecessary inner loops in your implementation. I think you could calculate the minimal difference via 2 not nested loops.
You don't need to calculate sums of parts on each iteration via loops, the idea is to modify sums by moving 1 array's element form one part to another on each iteration.
The following approach gives a time complexity of $$\O(N)\$$:

public int solution(int[] A)
{
// Sum of parts in the initial position:
int part1 = A[0];
int part2 = A.Sum() - part1;  // 1st loop
int min = Math.Abs(part1 - part2);

// Initial position is 1 since parts must be non-empty.
// Looping should be finished before the last element for the same reason.
for (int i = 1; i < A.Length - 1; i++)  // 2nd loop
{
int a = A[i];
// Move current element from part2 to part1:
part1 += a;
part2 -= a;
// Find the difference:
int val = Math.Abs(part1 - part2);
if (val < min)
{
min = val;
// Early exit condition:
if (min == 0)
{
break;
}
}
}
return min;
}


EDIT
Added early exit condition part1 >= part2, thanks to @Heslacher.
EDIT 2
Removed early exit condition part1 >= part2, since array elements can be negative.
EDIT 3
Since parts must be non-empty, loop limits should be deflated by 1. Thanks again to @Heslacher. EDIT 4
Fixed initial iteration. Thanks to @Timo.

• Where do you compare a[0] to the rest? You immediately add to part1 and subtract from p2.
– Timo
Sep 22, 2020 at 18:02
• @Timo Nice catch! Fixed. Thank you. Sep 22, 2020 at 22:48
• ok, you start from the left, Heslacher starts from the middle. I think it does not matter where to start. Could you have a look at the comments of heslacher's post, his code and give a hint if you can? [4,2,1,2] does not give the correct result for his code.
– Timo
Sep 23, 2020 at 7:56

Style

Initializing of multiple variables on one line removes readability.
Writing for loops on one line removes readability.

Dead code should be deleted (// p = i + 1)

Bug

It seems that you have a little unnoticed bug in your code. Your loop

for (int i = 0; i < A.Length - 1; i++) {


misses the last element of your array.

Problem

Let us assume we have an array A containing 8 elements like

3 5 7 2 5 2 1 3

The ideal divider would be if the arrays left half summed up would be equal to the right half summed up.
Unfortunatetly here

sumLeft = A[0] + A[1] + A[2] + A[3] == 17
sumRight = A[4] + A[5] + A[6] + A[7] == 11
difference = sumLeft - sumRight == 6

So as we see that the left half > right half let us take the last element of the left side and check if 2 * A[half-1] <= difference wich is 2 * 2 <= 6 so we can do

sumLeft = sumLeft - A[3] == 15
sumRight = sumRight + A[3] == 13
difference = difference - 2 * A[3] == 2

Or simplified for sumLeft > sumRight

difference = sumLeft - sumRight;
while (2*A[currentHalf-1] <= difference)
{
currentHalf = currentHalf -1;
sumLeft = sumLeft - A[currentHalf]
sumRight = sumRight + A[currentHalf]
difference = difference - 2 * A[currentHalf];
}


EDIT : Based on @Dmitry's comments I rechecked the algorithm and came to the result that this algorithm only works for positive numbers.

And my implementation of the above

public int solution(int[] A)
{
int length = A.Length;
int sumLeft = 0;
int sumRight = 0;

int currentArrayHalf = length / 2;

for (int i = 0; i < currentArrayHalf; i++)
{
sumLeft = sumLeft + A[i];
sumRight = sumRight + A[i + currentArrayHalf];
}

Boolean isEven = length % 2 == 0;

if (!isEven) { sumRight = sumRight + A[length - 1]; }

int step = 1;
if (sumLeft > sumRight)
{
step = -1;
if (isEven)
{
currentArrayHalf--;
}
}

int difference = Math.Abs(sumLeft - sumRight);
if (difference == 0) { return difference; }

while (currentArrayHalf >= 0 && currentArrayHalf < length && 2 * A[currentArrayHalf] <= difference)
{
sumLeft = sumLeft - A[currentArrayHalf];
sumRight = sumRight + A[currentArrayHalf];
difference = difference - 2 * A[currentArrayHalf];
currentArrayHalf = currentArrayHalf + step;
}

return difference;
}

• I translated the code to python, but it is not working regarding the correct diff. Can you have a close look?
– Timo
Sep 22, 2020 at 18:40
• I got this driver: [4,2,1,2]. 6>3, currentHalf=Pos. 2. If you switch the CurrentH to Pos. 1, you have the right separation: 4<5. But 2*2 is not < diff (=3), so you do not enter while.Tschüss.
– Timo
Sep 22, 2020 at 18:52
• .. and here is a java working example. So, my conclusion for small array sizes is using 2 inner loops as seen here, second function. But what about huge arrays..
– Timo
Sep 23, 2020 at 6:25
• @Timo, unfortunately I don't have the time right now to dig into this. Feel free to change the code in my answer. Sep 23, 2020 at 7:30