Tuesday, February 19, 2013

Codility Equi Task

Codility is a site that tests coders. Their demo problem task is called Equi. You can read the full description of the problem and solutions in a number of different languages on their blog post about it: Solutions for task Equi

I was somewhat surprise at the complexity of the code required in many languages. Using C#'s LINQ syntax makes it obvious and simple to write:

static int equi(int[] A)
{
    for (int i = 0; i < A.Length; i++)
    {
        if (A.Take(i).Sum() == A.Skip(i + 1).Sum())
        {
            return i;
        }
    }
    return -1;
}

It's also not difficult to modify that function to return all the equilibrium indexes: 

static IEnumerable<int> equi2(int[] A)
{
    for (int i = 0; i < A.Length; i++)
    {
        if (A.Take(i).Sum() == A.Skip(i+1).Sum())
        {
            yield return i;
        }
    }
}

Note that this solution although simple and elegant to write is not performant because the full array get summed in each loop. i.e. the time complexity of this solution is O(n^2). For a time linear solution you would increase and decrease a left and right sum variable as you moved through the index and compare those values.