Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

share|improve this question
2  
What does 83% mean? Does your code fail for some inputs? Or just that it's too slow? –  svick Jul 17 at 23:18
    

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
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 at 0:46
    
Why shouldn't 0 be the equilibrium index for {3, -1}? –  200_success Jul 18 at 4:18
    
The problem, at least on Codility, is asking for the lowest value, not an index. –  Daniel Mann Jul 18 at 12:36
    
@Daniel Thank you very much. –  user3708689 Jul 25 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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