# 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. – RubberDuck Nov 24 '14 at 14:52
• – 200_success Nov 24 '14 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)
{
int min = Int32.MaxValue;

// Sum of parts in the initial position:
int part1 = A[0];
int part2 = A.Sum() - part1;  // 1st loop
// 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.

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

• Array elements can be negative. Your method gives incorrect result in this case. Example: -3, -1, -2, -4, -3 gives 17 instead of 1. – Dmitry Nov 25 '14 at 6:14
• @Dmitry Thanks for the hint. I have tested it with negative values also, but not quite the right ones. Updated answer. – Heslacher Nov 25 '14 at 6:45
• The problem is still alive. Test for 300, -1, -2, -4, -3. Correct answer: 290, your new method returns 302. Another test case with the same correct answer: 300, 0, 0, 0, -1, -2, -4, -3. Try it too. – Dmitry Nov 25 '14 at 14:34
• @Dmitry, this seems to be right (about my algo), but yours has a flaw also if it is returning 290. Because the correct answer would be 296 as (300 + (-1) + (-2) + (-4)) -(-3) ==296, wouldn't it ? – Heslacher Nov 25 '14 at 14:54
• @Dmitry You are iterating on item to much. The assignment states: split into 2 non empty parts. Mine is wrong anyway ;-( – Heslacher Nov 25 '14 at 15:07