Solving for equilibrium index in an array

Question

I did a sample on Codility and finished the test task.

The problem description is very short:

The equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

$$A[0]=-7, A[1]=1, A[2]=5 ,A[3]=2, A[4]=-4, A[5]=3, A[6]=0$$

\$3\$ is an equilibrium index, because:

$$A[0]+A[1]+A[2]=A[4]+A[5]+A[6]$$

\$6\$ is also an equilibrium index, because:

$$A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0$$

(The sum of zero elements is zero) \$7\$ is not an equilibrium index - because it is not a valid index of sequence A. If you still have doubts, here is a precise definition: The integer \$k\$ is an equilibrium index of a sequence \$A[0],A[1]\dots,A[n-1]\$ if and only if \$0\le k\$ and \$\sum(A[0\dots(k-1)])=\sum(A[(k+1)\dots(n-1)])\$. Assume the sum of zero elements is equal to zero.

The code I wrote gives the correct result, but, I only scored 8% on correctness and a 54% on performance. Here is my code:

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {


    // write your code in JavaScript (Node.js 4.0.0
    var arrLen = A.length;

    var i = 0;



    for(i = 0; i < arrLen; i++){

        //console.log("i: " + i);

         var firstSum = 0;
        var secSum = 0;

        var currIndex = i + 1;

        //get first chunk
        var j = 0;
        var lenJ = currIndex;

        for(j = 0; j < lenJ; j++){

            //console.log("firstChink: " + j);
            firstSum += A[j];

        }


        //get second chunk
        j = currIndex + 1;
        lenJ = arrLen;

        for(j; j < lenJ; j++){

            //console.log("secChunk: " + j);
            secSum += A[j];

        }

        if(firstSum == secSum){

            return currIndex;

        }



    }


    return arrLen;

}

Can somebody explain why my code scored so low? And what to do to improve?

Answer 1

I'm piggy backing on @jonah's answer. The first code snippet returns what Codility is asking for: any equilibrium index. Second code snippet returns all answers like in @jonah's suggestion. I also added two accumulating arrays for side by side comparison. You can add a breakpoint at the end of the function to compare the two arrays.

var A = [-1, 3, -4, 5, 1, -6, 2, 1];

function solution(A) {        
    var rightSum = A.reduce((acc, val) => acc + val, 0), leftSum = 0;
    
    for (var i = 0; i < A.length; i++) {
        
        rightSum -= A[i];

        // Codility is asking for any, so return first found
        if (rightSum === leftSum) return i; 
        
        leftSum += A[i];
    }
    
    return -1;
}

solution(A);

var A = [-1,3,-4,5,1,-6,2,1];

function solution(A) {
    
    var rightSum = A.reduce((acc, val) => acc + val, 0), leftSum = 0, rightSums = [], leftSums = [], answers = [];
    
    for (var i = 0; i < A.length; i++) {
        
        rightSum -= A[i];
        
        // You can keep track of answers for comparison/debugging
        rightSums.push(rightSum);
        leftSums.push(leftSum);
        
        if (rightSum === leftSum) answers.push(i);
        
        leftSum += A[i];
        
    }
    
    return answers;
}

solution(A);

Answer 2

Correctness:

Your code has a few syntax points that are bad form, and your indentation and spacing is incorrect in more than a few places (for example, the massive amount of extraneous lines)

You should consider using a code cleaner, like JSFiddle's TidyUp to tidy your code up, and you can inspect the changes made to learn to improve, but a few major ones are as follows:

for loop:

var arrLen = A.length;

var i = 0;



for(i = 0; i < arrLen; i++){

A for loop has the built-in feature to define variables, and not just more than one, in which case, this can be converted to the following: (Additionally, you shouldn't sacrifice readability for a few characters, arrLen is fine as arrayLen or arrayLength)

for(var i = 0, length = A.length; i < length; i++){

Clarity of variables:

function solution

solution is unclear, consider improving that with something like: equiSolution or equi. secSum is a bit ugly unclear, and for sakes of readability, a few characters won't hurt.

Getting Chunks:

Similarly to the for loop point above: you shouldn't need to define lenJ, or manually define j:

for (var j = 0, length = i + 1; j < length; j++){
    firstSum += A[j];
}

for(var j = i + 2, length = A.length; j < length; j++){
    secondSum += A[j];
}

console.log:

Instead of blind commented-out logs everywhere, use a debug variable with a helper function:

function log(string){
    var debug = true;
    if (debug) console.log(string);
}

// ...
log("firstChink: " + j); //<-- also spelling mistake here

With that helper function in place you can just change the debug variable if you want them not to be logged. Ideally, you would keep that debug variable as a constant at the top of the program, but for a small script like this, probably not necessary.

Returning -1:

In the case that there is no equilibrium in the array, -1 is supposed to be returned, however, instead you're returning arrLen (the length of the array). Returning the array length will cause test failure in those cases.

---

Performance:

\$O(n^2)\$ solution:

Your solution is currently \$O(n^2)\$, meaning the operation is processed however many elements there are squared, while the Codility page explains how an \$O(n)\$ solution can be attained:

Instead of using a solution where you check the sums of both sides relative, use the following rule:

\$S_R\$ = sum of right side, \$S_L\$ = sum of left side, \$S_T\$ = total sum, \$A[i]\$ = the current element

$$S_R = S_T - S_L - A[i]$$ $$S_L = S_T - S_R - A[i]$$

So, simply use sums alongside the following algorithm, which has actually been supplied by Codility in their Equi blog post, you'll be able to achieve \$O(n)\$:

long long sum_left = 0;    
for(i=0;i<n;i++) {
    long long sum_right = sum - sum_left - (long long) arr[i];
    if (sum_left == sum_right) return i;
    sum_left += (long long) arr[i];
}

One major downside:

JavaScript is not made to handle the long or long long types, so arrays with larger sums will not be able to handle this as well.

This is a language feature; however third party libraries can supply the type, if you so wish. See this Stack Overflow answer for more information on the subject.

Answer 3

Quill's answer does a good job explaining the performance problems of your approach.

I thought I'd add a working javascript solution that is fairly concise, with explanations inline as comments. Note that this function returns an array of all equilibrium indexes, or the empty array if none are found:

function eqIndexes(arr) {
    // start the right hand sum as the sum of the whole array
    var rightSum = arr.reduce(function(m,c) { return m+c }, 0),
        leftSum = 0,
        isEndPoint;

    // Here we use reduce to build up an array of all
    // indexes which have an equilibrium
    return arr.reduce(function(answer,cur,i) {
        rightSum -= cur;
        isEndPoint = i == 0 || i == arr.size -1
        // If we're at the beginning or the end of the array,
        // just return the answer we already have.  This will 
        // be the empty array we started with when i == 0, and 
        // it will be our final answer when we're at the last elm.
        if (isEndPoint) return answer;

        leftSum += arr[i-1];
        if (leftSum == rightSum) answer.push(i);
        return answer;
    },[]);
}