6
\$\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
  • 3
    \$\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, 2014 at 14:52
  • 2
    \$\begingroup\$ See Plain English explanation of Big O. \$\endgroup\$ Nov 24, 2014 at 19:55

2 Answers 2

6
\$\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)
{
    // 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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Where do you compare a[0] to the rest? You immediately add to part1 and subtract from p2. \$\endgroup\$
    – Timo
    Sep 22, 2020 at 18:02
  • \$\begingroup\$ @Timo Nice catch! Fixed. Thank you. \$\endgroup\$
    – Dmitry
    Sep 22, 2020 at 22:48
  • \$\begingroup\$ 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. \$\endgroup\$
    – Timo
    Sep 23, 2020 at 7:56
7
\$\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\$
4
  • \$\begingroup\$ I translated the code to python, but it is not working regarding the correct diff. Can you have a close look? \$\endgroup\$
    – Timo
    Sep 22, 2020 at 18:40
  • \$\begingroup\$ 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. \$\endgroup\$
    – Timo
    Sep 22, 2020 at 18:52
  • \$\begingroup\$ .. 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.. \$\endgroup\$
    – Timo
    Sep 23, 2020 at 6:25
  • \$\begingroup\$ @Timo, unfortunately I don't have the time right now to dig into this. Feel free to change the code in my answer. \$\endgroup\$
    – Heslacher
    Sep 23, 2020 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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