Nested Loop Perfromance

[reastwood]

How would I improve the performance here?

This is the takeEquilibrium problem. I want to take multiple points on a tape, find the absolute difference of the positions to the left minus those to the right and return the min value.

Maybe the nested loop is unnecessary? The solution returns the correct answers but It is failing performance tests.

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++11
    int sumLeft = 0;
    int sumRight = 0;
    int result = -1;
    
    for (std::vector<int>::iterator it = A.begin(); it != A.end(); it++)
    {
        for (std::vector<int>::iterator iter = A.begin(); iter != A.end(); iter++)
        {
            if (iter <= it)
                sumLeft+=*iter;
            else
                sumRight+=*iter;
        }
        int tmp = abs(sumLeft - sumRight);
        
        if (result < 0 || tmp < result)
            result = tmp;
        
        sumRight = 0;
        sumLeft = 0;
    }
    
    return result;
}

[keskiverto]

Your problem description is not clear.
Do you mean this: http://blog.codility.com/2011/03/solutions-for-task-equi.html

[dhayden]

If you sort the vector first then the items that are less on the ones on the left and the items that are greater are the ones on the left.

Next, create a second vector called runningSum. runningSum[i] is the sum of A[0] through A[i].

Now for any element A[j], the sum of all elements less than A[j] is runningSum[j-1]. The sum of all elements greater than A[j] is A[A.size()-1] - A[j].

Total running time is bound by the sort time so it's O(n*log(n))