5
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – RubberDuck Nov 24 '14 at 14:52
  • \$\begingroup\$ See Plain English explanation of Big O. \$\endgroup\$ – 200_success Nov 24 '14 at 19:55
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Array elements can be negative. Your method gives incorrect result in this case. Example: -3, -1, -2, -4, -3 gives 17 instead of 1. \$\endgroup\$ – Dmitry Nov 25 '14 at 6:14
  • \$\begingroup\$ @Dmitry Thanks for the hint. I have tested it with negative values also, but not quite the right ones. Updated answer. \$\endgroup\$ – Heslacher Nov 25 '14 at 6:45
  • \$\begingroup\$ 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. \$\endgroup\$ – Dmitry Nov 25 '14 at 14:34
  • \$\begingroup\$ @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 ? \$\endgroup\$ – Heslacher Nov 25 '14 at 14:54
  • 1
    \$\begingroup\$ @Dmitry You are iterating on item to much. The assignment states: split into 2 non empty parts. Mine is wrong anyway ;-( \$\endgroup\$ – Heslacher Nov 25 '14 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.