# TapeEquilibrium implementation does not satisfy all requirements

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%.

-
What does 83% mean? Does your code fail for some inputs? Or just that it's too slow? – svick Jul 17 '14 at 23:18
This meta post explains why we ask for problem statements to be included in the question. – RubberDuck Jul 18 '14 at 0:58
@svick This is a bit "after the fact", but 83% is referring to something like this - where my results got 91%. – WernerCD Jun 24 '15 at 14:04

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

-
Welcome to CR! Remember that users with less than 15 rep cannot yet spend votes; if you can answer a question, you should also upvote that question, so that the OP can upvote your answer in return! Nice first post BTW! ;) – Mat's Mug Jul 18 '14 at 0:46
Why shouldn't 0 be the equilibrium index for {3, -1}? – 200_success Jul 18 '14 at 4:18
The problem, at least on Codility, is asking for the lowest value, not an index. – Daniel Mann Jul 18 '14 at 12:36
@Daniel Thank you very much. – user3708689 Jul 25 '14 at 20:27

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.

-

## protected by Jamal♦Aug 15 '15 at 5:14

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).