TapeEquilibrium implementation does not satisfy all requirements

Question

The Codility's TapeEquilibrium problem asks:

Given an array \$A\$ with length \$N\$, indexed starting from 0, find an equilibrium index \$P\$, such that

$$\left| \sum_{i=0}^{P-1} a_i - \sum_{i=P}^{N-1} a_i \right|$$

is minimized. Assume that \$2 \le N \le 100000\$ and that \$-1000 \le a_i \le 1000\$. Elements of input arrays can be modified.

Here is my solution:

 public int solution(int[] A)
 {
        // write your code in C# 5.0 with .NET 4.5 (Mono)
        List<int> list = A.Cast<int>().ToList();
        int temp = 0;
        int sum = list.Sum();
        List<int> result = new List<int>();
        foreach (int i in list)
        {
             temp = temp + i;           
             result.Add(Math.Abs(  ( sum - temp) - temp)); 

        }
        return  result.Min();
    }

How can I make it better? I only got 83%.

Answer 1

I coded up my own solution, and mine was pretty close to yours, but mine received 100%.

Here are the problems:

List<int> list = A.Cast<int>().ToList();

Both the Cast and the ToList are redundant here. Arrays implement IEnumerable, which is enough for LINQ. The ToList is iterating the entire array, which is costing you some runtime.

int temp = 0;
int sum = list.Sum();
List<int> result = new List<int>();
foreach (int i in list)
{
    temp = temp + i;           
    result.Add(Math.Abs(  ( sum - temp) - temp)); 
}
return  result.Min();

This is hurting you on the space requirements -- you're generating a list of every subtraction. Then it's hurting you on time requirement again because it has to iterate the entire result list to find the lowest number.

You can do the entire thing with two passes of the input. You're doing 4.

I'll also say that you should almost never have a variable named temp. Give it a name that describes what it actually is. I used the names "left" and "right".

Left starts at 0, Right starts at the Sum. For each number, add it to Left, subtract it from Right. Much easier to read.

Update I actually realized that in addition to everything I said, there's a major logic flaw in your version, which is probably what's hurting you more than the other stuff:

What happens if your code tries to handle {3, -1}?

First pass:

temp = 3 sum = 2

|(2 - 3) - 3| = 4

There should be no second pass, but you do one anyway: Second pass:

temp = 2 sum = 2

|(2 - 2) - 2| = 2

Answer 2

I'm a bit confused as to how you're getting 83%. result.Min() is giving you the minimum value of result, whereas from your problem statement you are supposed to be returning the index that gives you that value.

Generally, with that and the improvements from Daniel Mann's answer in mind, your approach is good. With a question like this, there's not much "clever" you can do to improve performance in even the average case. Divide-and-conquer type techniques won't really work because you can't evaluate how useful a segment of the array is without just iterating over it, and by then you haven't saved any time.

For example, you could terminate your loop early if the difference between your current result and your best result so far is greater than (1000*the numer of remaining items in the list), but it's highly questionable whether that situation would arise often and early enough to actually improve performance on average.