I was looking at the demo Equi task on Codility last night and scored 12/100 for the following function:

function solution(A) {
    var n = A.length;
    var p = 0;
    var sum = 0;
    var sumLeft = 0;
    var sumRight = 0;
    var equilExists = 0;

    if (n == 0) {
        return -1;
    }

    for (i=0; i<=n; i++) {
        sum = A[i];
        for (j=0; j<=n; j++) {
        if (j < i) {
            sumLeft += A[j];
        } else if (j > i) {
            sumRight += A[j];
        }
        if (sumLeft == sumRight) {
            equilExists = 1;
            p = i;
            return p;
                }
        }
    }

    if (equilExists == 0) {
        return -1;
    }
}

For those of you not familiar with the task it can be found at .html

I was wondering if anyone could help point out where my solution falls down?

Many thanks!

I was looking at the demo Equi task on Codility last night and scored 12/100 for the following function:

function solution(A) {
    var n = A.length;
    var p = 0;
    var sum = 0;
    var sumLeft = 0;
    var sumRight = 0;
    var equilExists = 0;

    if (n == 0) {
        return -1;
    }

    for (i=0; i<=n; i++) {
        sum = A[i];
        for (j=0; j<=n; j++) {
        if (j < i) {
            sumLeft += A[j];
        } else if (j > i) {
            sumRight += A[j];
        }
        if (sumLeft == sumRight) {
            equilExists = 1;
            p = i;
            return p;
                }
        }
    }

    if (equilExists == 0) {
        return -1;
    }
}

For those of you not familiar with the task it can be found at http://blog.codility./2011/03/solutions-for-task-equi.html

I was wondering if anyone could help point out where my solution falls down?

Many thanks!

• javascript
• sum

11 Answers 11

The biggest problem with your solution is that nested loop.

You iterate over the whole array at each index to calculate the sum of left and right parts at current index. One of their requirements is O(n) plexity, while yours is O(n^2) (i think).

You only need to loop over the array twice: once to get the sum of elements and once to find the equilibrium. At the start of the second loop the sum on the left == 0 and the sum on the right == total. Iterating over the elements you just need to update the sums: the right sum = total - left sum - value at the current index, then you pare if right == left and if not - the left sum grows by the value at current index.

I've scored 100pts for this one:

function solution(A) {
  var total = (function(a){ var l = a.length, s = 0; while(--l>-1){ s+=a[l] } return s; }(A)), 
  eq = -1, 
  l = A.length, 
  Lsum = 0, 
  Rsum = 0; 
  A.forEach(function(n,i){ 
    Rsum = total - Lsum - n; 
    if(Rsum == Lsum){ eq = i; /* in fact no need to continue, should terminate here. */ } 
    Lsum += n; 
  }); 
  return eq;
}

JS solution Scores - 100% and performs pretty fast

function solution(A) {
   const values = new Set(A) // dedupe array
   let i = 0
   while(++i) { // iterate from 1, the first possible positive integer greater than 0 
       if(!values.has(i)) { // check if set has value and break loop if it does not
           break
       }
   }
   return i
}

Your solution fails mainly due to the reason that it can always detect only the first index which is in equilibrium.

For example, if there is a sequence having equilibrium at index 3 and 6 both, but if we apply your solution to this sequence then it will always return 3 only and never provide 6 also as an answer.

This is due to the reason that you are not storing anywhere the indices already found to be in equilibrium and moving ahead of them. Either you need to use recursion or maintain some storage for indices already found to be having equilibrium and modify your solution accordingly to catch all such indices and not just the first one.

Also, there are few variables defined but never used in your answer, like sum variable, causing an unessential overhead.

First of all, your function always returns 0 (if n>0). This is because you put the if (sumLeft == sumRight) inside the inner for-loop.
If you fix this, you still have a problem, because the variables sumLeft and sumRight are not initialized before the inner for-loop. If you fix these problems, the function is at least correct, and it scores 75 points. However, your algorithm is clearly quadratic. To remedy this you would have to ask yourself how the left and right sum change when you increase i by one. Is it necessary to recalculate both from scratch?

class Solution {
public int solution(int[] A) {
    if(A.length < 1) {
        return -1;
    }
    double leftSum = 0, sum = 0;
    for(int i=0; i<A.length; i++) {
        sum += A[i];
    }
    for(int i=0; i<A.length; i++) {
        if(leftSum == sum - leftSum - A[i]) {
            return i;   
        }
        leftSum += A[i];
    }
    return -1;
}

}

My JavaScript solution...

 function solution(A) {

    var length = A.length;

    // special case to void total calculation
    if(!length) return -1;

    var lSum = 0;
    var rSum = 0;
    var i    = 0;

    // get total
    for(; i < length; rSum += A[i++]);

    // reset iterator
    i = 0;

    for(; i < length; i++) {
        rSum -= A[i];
        if(rSum === lSum) return i;
        lSum += A[i];        
    }

    return -1;
}

My answer is this one:

function balance(arr){

var N = arr.length;
if (N == 0){ return -1};

var suma = 0;
for (var i=0; i<N; i++){
    suma += arr[i];
}

var suma_iz = 0;
for(i=0; i<N; i++){
    var suma_de = suma - suma_iz - arr[i];
    if (suma_iz == suma_de){
        return i};
    suma_iz += arr[i];
}

  return -1;}

This solution satisfy the O(n) requirement

A slightly different one (100pts):

function solution(list) {
  var length = list.length,
      sumRight,
      sumLeft = 0,
      equi_index = -1;

  if (length === 0) {
    return equi_index;
  } else if (length === 1) {
    return 0;
  }

  var total = (function(){
    var sum = 0;
    while (length--) {
      sum += list[length];
    }
    return sum;
  })();

  list.some(function(each, index){
    sumRight = total - sumLeft - each;
    if (sumLeft === sumRight) {
      equi_index = index;
      return true; // stop iteration
    }

    sumLeft += each;
  });

  return equi_index;
}

I scored 100% with this solution, it is in C++ but you'll see the algorithm. The first thing I do is to create a vector of the running sum of the array, I then use this to check for the edge cases first, then loop the whole array for the first equi index. The plexity will then always be O(n).

#include <vector>

using namespace std;

long long Sum(vector<int>::const_iterator begin, vector<int>::const_iterator end, vector<long long>& sums)
{
    long long sum = 0;
    for(vector<int>::const_iterator it = begin; it != end; it++)
    {
        sum += (long long) (*it);
        sums.push_back(sum);
    }
    return sum;
}

int solution(vector<int> &A)
{
    vector<long long> sums;

    long long allSum = Sum(A.begin(), A.end(), sums);

    int N = sums.size();

    if(N==0)
        return -1;

    if(N==1 && allSum == 0)
        return 0;

    if(N > 1)
    {
        if(sums[N-2] == 0)
            return N-1;
    }

    if((allSum- sums[0]) == 0)
        return 0;

    long long prefixSum = 0;
    for(int i = 1; i < N; ++i)
    {
        prefixSum = sums[i-1];

        if(prefixSum == 0 && i == N-1)
            return i;

        if(prefixSum == (allSum - sums[i]))
            return i;
    }

    return -1;
}

\\ Javascript solution
function solution(A) {
    const sortAry = A.sort((a, b) => a - b);
    var initVal = 1;
    for (let i = 0; i < sortAry.length; i++) {
        if (sortAry[i] <= 0) continue;
        if (sortAry[i] < initVal) continue;
        if (sortAry[i] === initVal) {
            initVal += 1;
        } else {
            return initVal;
        }
    }
    return initVal;
}

Edit 06/23: I came back to this post after reviewing my SO history and was curious about it again. While my solution and the one that inspired it above (the JS Set()-based solution posted by Edward Irby) passed when tested and seemed correct on what I read, I took a look back at things and I think something got mixed up somehow and some of us were posting code for a different problem than the one originally posted.

Unfortunately the link is now dead and the version I viewed that also allowed you to submit code for immediate testing is seemingly not archived.

I did indeed even mention in my original post below that I was questioning whether the problem and/or it's description and/or requirements had somehow changed from its original posting to when I had visited the page (and at that time it included a feature to post and test your code immediately) as most of the other solutions posted didn't seem to line up with the Set()-based solution posted by Edward Irby.

After reviewing the problem description (at least, the version that I can still see on the web archive) itself makes one think that the Set()-based solution (as well as mine and other newer ones) couldn't possibly be correct.

I'll quote the problem here (the older/original version that I can find on web archive) here for posterity before I continue:

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 page further goes on to describe the expected solution:

Write a function

int equi(int A[], int n)

that, given a sequence, returns its equilibrium index (any) or -1 if no equilibrium index exists. Assume that the sequence may be very long.

Again, unless the requirements had changed this alone should invalidate both the Set()-based solution and mine. Neither of us is taking two parameters (although n is just seemingly used to set an index limit for the provided array you could potentially use .length, though other solutions that are 'correct' also don't have the second n parameter either) - also, neither of the solutions return -1 in the fail case.

Also, based on the above quoted description of the problem, the Set()-based solution, because it's a Set(), de-duplicates the array. Based on the problem description quoted above, I see no requirements for this and indeed if the supplied array was intended to have duplicate values then this solution would fail in that case as well.

Reviewing this, I feel it's quite likely that we somehow got redirected to a pletely different problem, though the one I see on the web archive that I quoted above does feel familiar to me.

Going further, I decided to test and pitted the solution posted by pawel against Edward Irby's Set()-based solution and my own (after fixing it to return i instead of A) using the array provided in the problem description.

Modifying pawel's solution to add all accepted solutions to an array and return that instead, it correctly returns both the possible solutions quoted above: [3, 6].

Both Edward Irby's Set()-based solution and my own returned 4; I suppose this could be correct if you did -1 first before returning but that doesn't even make sense. I also modified mine to have it attempt to return an array containing the appropriate solutions to see if I perhaps got [4,7], which it of course didn't nor was I really expecting it to.

Even a solution posted by user13557870 results in the same answer as mine and the Set()-based solution and also never returns -1, which leads me to believe even more that the problem changed or the link redirected to a new/different problem.

So after wasting time and looking at this for the last hour or so, it truly seems like newer posted solutions (mine was 2022, Edward Irby's Set() was 2021, user13557870's was 2020 but pawel's was 2013!

After running thousands of iterations of random arrays with length=7 and a random length between 2 and 1000, trying both with arrays containing and not containing negative numbers:

• All the later posted solutions I tested including mine, Edward Irby's Set() and user13557870's, from 2020 onwards, return the same result as each other - every single time but never matched the below tested earlier solutions.
• All the earlier posted solutions that I tested (up to 2016) also always return the same result as each other and also never matched the above tested newer solutions.

This I'm absolutely convinced now that the answers and code in this post are answering two different questions based on when they were added. Of course, the OP posted in 2013 and would've seen the original question as archived and quoted above.

It seems I was already suspicious of this in my original post when seeing some of the original answers as I even mentioned this in my original post and through the aforementioned investigation, I'm not sure what else could've happened.

Unfortunately while the link does have newer archive entries, it is seemingly one of those (crappy method IMO) pages that fully relies on client-side rendering and thus they either return a 404 (middle-ish ones) or do not load at all (newest ones) - this means I have no idea what the definition of the problem I was actually trying to solve was.

I will leave my original post below for posterity, curiosity and archival purposes. Unfortunately, while it was a correct answer in the context of the challenge as provided when I clicked the link originally to view it, it's not a correct answer in the context of the OP's ask of the challenge/problem since it's now clear they'd have seen the original version of it as quoted above and archived and not the version I saw.

Note to any Mods: Perhaps in light of the fact that the link to the challenge/problem is now defunct and the OP did not include the full description of the problem in their post, maybe this answer should now be locked/archived. Also, perhaps in addition or opposition to that, you could add my quotation of the original problem to the OP's post to clarify.

My Original Post

I can't believe how long some of the answers here are; maybe I just think differently..?

Perhaps the test has changed or something since this thread was created..?

Edit 06/23: Updated to what it should've been (see above edit) - below is also the original code I posted.

//updated/fixed 06/23
function fixedSolution(A) {
  for (let i=1;i<A.length-1;++i)
    if (!A.includes(i)) return i;
}

//original solution I posted
function solution(A) {
  for (i=1;i<100000;i++)
    if (!A.includes(i)) return A;
}

I see one other similar solution but the dedup feels unneeded. Edit: The conversion to Set/hash and dedup actually scores 100% for performance where mine doesn't. Weird!

Edit: So I did some benchmarking. My solution is an order of magnitude faster any size arrays with smaller values. The Set solution is faster with arrays that have larger internal values.

Array length: 400000 of random values up to 40000
Call to MySolution took 5218.896612003446 milliseconds
Call to NotMySolution took 226.6879480034113 milliseconds
Array length: 600000 of random values up to 1000
Call to MySolution took 40.543023988604546 milliseconds
Call to NotMySolution took 204.18921500444412 milliseconds

This does show that, at least NodeJS handles sets more efficiently and predictably. Interesting result though. Though I shouldn't be surprised the more memory intensive solution could be faster. Although technically there's one test missing; the actual test states that the return value should not exceed 100,000, however, any value of the array can be upto 1,000,000 .. thus the Set() solution actually should fail but for some reason this test is missed..?

2 lines of code. I'd actually normally probably write it in a single line with a ternary but you can't use a return in a tern, you can return a tern but in a loop, that'll return first iteration. Technically could be one anyway.

Edit (06/23): Another ment on my original post: I don't know what I was thinking saying "you can't use a return in a tern"; while I suppose it's technically to say that you can't use a return inside a tern, you can use a tern to set a return value (eg. return (true)?a:b;), so perhaps I should've wrote this more clearly - though that technicality still prevents it from being used to break out of a loop.

Edit: I didn't notice the actual assessment in the end. Obviously there could be more performant methods and this doesn't score full performance points but in reality, especially with JS, we're not after every CPU cycle and I think readability and maintainability are as if not more important.

Edit (06/23): Just a note that the above un-dated edit about the assessment was done shortly after my original post and is not part of my 06/23 update.