Friday, March 25, 2011

Solutions for task Equi

One of our most frequently solved tasks is Equi. It is one of our demo problems (freely available without registration). As of today, we have evaluated over 50,000 solutions to this problem.
The most popular language used for solving this problem is Java, though of course C#, PHP and C++ are also very popular:
Programming language Solutions count
Java18,021
C#8,105
PHP6,350
C++6,042
C 4,208
Python 4,151
Ruby 1,915
JavaScript 1,107
Perl 774
Pascal 760
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]..,A[n-1] if and only if 0<= k and sum(A[0..(k-1)])=sum(A[(k+1)..(n-1)]). Assume the sum of zero elements is equal to zero.

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.
The problem can be solved by using various approaches, the most common being simply to follow the equilibrium definition:
int equi ( int A[], int n ) {
    int k, m, lsum, rsum; 
    for(k = 0; k < n; ++k) { 
        lsum = 0; rsum = 0;
        for(m = 0; m < k; ++m) lsum += A[m]; 
        for(m = k + 1; m < n; ++m) rsum += A[m];  
        if (lsum == rsum) return k;
    } 
    return -1; 
} 
Unfortunately, this approach has two disadvantages:
  • it fails on large input data sets, since the time complexity is O(n2)
  • it fails on large input values (for example if the input array contains values like MIN/MAX_INT) due to the arithmetic overflows
The solution analysis will detect such problems in submitted code: We can fix the first problem with a better algorithm, and the second problem with a better data-type (for example, using long long type instead of int for sum computations). The key observation for better running time is to update the left/right sums in constant time instead of recomputing them from the scratch.
int equi(int arr[], int n) {
    if (n==0) return -1; 
    long long sum = 0;
    int i; 
    for(i=0;i<n;i++) sum+=(long long) arr[i]; 

    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];
    } 
    return -1; 
} 


Using this solution, you can obtain a perfect score:


What's next?

We offer two other different demo problems on our site: We also launched a contest for the shortest Equi solution. Try it now..

125 comments:

  1. Java solution, having said that I am not 100% sure what it's meant to return if the two sides are equal. I just set it to return what the sides are equal to. I haven't tested this properly but it should work for large inputs.

    public static int equi(int A[], int k)
    {
    if(0<=k) {
    int sum1 = 0;
    int sum2 = 0;
    for(int i = 0; i < k; i++) {
    sum1 += A[i];
    }
    for(int i = k+1; i < A.length; i++) {
    sum2 += A[i];
    }
    if(sum1 == sum2) {
    return sum1;
    }
    }
    return -1;
    }

    ReplyDelete
    Replies
    1. It won't work with large inputs because u have "int" in type of sum...

      Delete
    2. This is a 100 points solution for java:
      public int equi( int[] A ) {
      long sum = 0;
      long leftSum = 0;

      for (int i=0;i<A.length;i++){
      leftSum += A[i];
      }
      for (int i=0;i<A.length;i++){
      if (sum==leftSum-A[i]) return i;
      sum+=A[i];
      leftSum-=A[i];
      }
      return -1;

      }

      Delete
    3. You are running twice over this array, you can do it better!
      Try counting from both sides and always try yo keep the sum of 0, just move where ever is better. Something like this:

      int equi(int arr[]) {
      int n = arr.length;
      if (n <= 0)
      return -1;

      long sum = arr[0] + arr[n - 1];
      for (int leftcount = 0, rightCount = n - 1; leftcount < rightCount - 1;) {
      long tmpLeftSum = sum + arr[leftcount + 1];
      long tmpRightSum = sum + arr[rightCount - 1];

      if(Math.abs(tmpLeftSum) <= Math.abs(tmpRightSum)){
      leftcount++;
      sum = tmpLeftSum;
      }
      else{
      rightCount--;
      sum = tmpRightSum;
      }

      if(rightCount - leftcount == 1 && sum == 0){
      return leftcount + 1;
      }

      }
      return -1;
      }

      Delete
    4. I can't imagine this returns the correct equi. Why deciding on which side to continue summing up (incrementing leftcount or rightCount) based on the current left and right temporary sum? And you overwrite sum all the time o_O

      The more I look at your code, the more mistakes I find. You shall have a look at the task description once again.

      Delete
    5. Pablos solution is good, but could it brake if long grows too big. Having a lot of Integer.MAX_VALUE.

      This would make it a bit safer:
      public int equi(int[] A) {
      BigDecimal sum = new BigDecimal(0);
      BigDecimal leftSum = new BigDecimal(0);

      for (int i = 0; i < A.length; i++) {
      leftSum=leftSum.add(new BigDecimal(A[i]));
      }
      for (int i = 0; i < A.length; i++) {
      if (sum.compareTo(leftSum.add(new BigDecimal(-A[i])))==0)
      return i;
      sum=sum.add(new BigDecimal(A[i]));
      leftSum=leftSum.add(new BigDecimal(-A[i]));
      }
      return -1;
      }

      Delete
    6. This solution achieves 100 score. The fastest way is to perform an initial sum and then just add to the left side and subtract from the right side. That way you only iterate the list twice, achieving O(2n) performance.

      int equilibriumIndex = -1;
      int potentialEqIdx = 0;

      long lowerSum = 0l;
      long upperSum = 0l;

      for(int j = potentialEqIdx+1; j < A.length; j++) {
      upperSum += A[j];
      }

      while(potentialEqIdx < A.length) {

      if(potentialEqIdx > 0 ) {
      lowerSum += A[potentialEqIdx-1];
      }

      if(potentialEqIdx+1 > 1) {
      upperSum = (upperSum - A[potentialEqIdx]);
      }

      if(lowerSum == upperSum) {
      equilibriumIndex = potentialEqIdx;
      break;
      }
      ++potentialEqIdx;

      }

      return equilibriumIndex;

      Delete
    7. I don't think this works for this case {-7,-1,-5,-2, 4, -3,0}
      should return 1 since P[0] == P[1]+P[2]+P[3]+P[4]+P[5]+P[6] but it returns -1...

      Delete
    8. @Victor: if it returns one then we should have P[0] == P[2] + ... + P[6], so excluding P[1]. Hence, -1 is a correct result.

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. # Python solution

    def equi(A):
    ````total_sum = sum(A)
    ````prev, curr = 0, A[0]

    ````for index in range(1, len(A)):
    ````````prev += A[index - 1]
    ````````curr += A[index]

    ````````if prev + curr == total_sum:
    ````````````return index

    ````return -1

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. This comment has been removed by the author.

      Delete
    3. This comment has been removed by the author.

      Delete
    4. def equi(A):
      ____for i in range(1,len(A)):
      ________if sum(A[0:i]) == sum(A[i+1:len(A)]):
      ____________return i
      ____return -1

      Delete
    5. Abner, this solution only received 25/100 points on the contest. Gets the wrong answer for extremely large numbers, extremely large negatives, overflow cases and pyramids, among others.

      Delete
  5. What is the correct solution for Equi([0,0,0]) ?

    ReplyDelete
  6. #PYTHON#
    #75% Analysis_Runtime

    def equi(A):
    ````````if A==[]:
    `````````````````return -1
    ````````length=len(A)
    ````````mid=length//2
    ````````s=sum(A)
    ````````if s-A[0]==0:
    ````````````````return 0
    ````````if s-A[length-1]==0:
    ````````````````return length-1
    ````````for i in range(length)[1:length-1]:
    ````````````````si=s-A[i]
    ````````````````if i<mid:
    ````````````````````````if si==sum(A[:i])*2:
    ````````````````````````````````return i
    ````````````````else:
    ````````````````````````if si==sum(A[i+1:])*2:
    ````````````````````````````````return i
    ````````return -1

    ReplyDelete
  7. def equi(A):
    ````n = len(A)
    ````if n == 0:
    ````````return -1
    ````total = sum(A)
    ````lsum = 0
    ````rsum = total
    ````for i in range(n):
    ````````rsum -= A[i]
    ````````if lsum == rsum:
    ````````````return i
    ````````lsum += A[i]
    ````return -1

    ReplyDelete
  8. In c# aditional solution is to work on pointers but the author don't allow to use "unsafe" block

    ReplyDelete
  9. // Solved @Mangatur

    using System;
    // you can also use other imports, for example:
    // using System.Collections.Generic;
    class Solution {
    public int equi ( int[] A ) {
    long sum = 0;
    int i = 0;
    for (i = 0; i < A.Length; i++)
    {
    sum += (long) A[i];
    }

    long sum_left = 0;
    for (i = 0; i < A.Length; i++)
    {
    long sum_right = sum - sum_left - (long) A[i];
    if (sum_left == sum_right)
    {
    return i;
    }
    sum_left += (long) A[i];
    }
    return -1;
    }
    }

    // post @ArtDuane (June 08, 2011)

    ReplyDelete
  10. Hi Bartosz,

    I use C# for solution in sample test.
    Above is the code you can verify.

    Best Regards,
    Duane Aritonang
    www.ArtDuane.com

    ReplyDelete
  11. Python solution in O(n)

    def equi ( A ):
    gtotal = sum(A)
    j = gtotal
    k = 0
    ctr = 0
    for i in A:
    j = j -i
    if j == k: return ctr
    k = k + i
    ctr += 1
    return -1

    ReplyDelete
  12. Python solution in O(n),

    def equi ( A ):
    ''''gtotal = sum(A)
    ''''j = gtotal
    ''''k = 0
    ''''ctr = 0
    ''''for i in A:
    ''''''j = j -i
    ''''''if j == k: return ctr
    ''''''k = k + i
    ''''''ctr += 1
    ''''return -1

    ReplyDelete
  13. Perfect Score 100 / 100 with JAVA O(n)
    class Solution {
    int equi ( int[] A ) {
    long sum = 0, leftsum = 0;
    int i, l = A.length;
    for(i = 0; i < l ; i++){
    sum += A[i];
    }
    for(i = 0; i < l ; i++){
    sum -= A[i];
    if(leftsum == sum){
    return i;
    }
    leftsum += A[i];
    }
    return -1;
    }
    }

    ReplyDelete
  14. So what's that C++ standard library that the task description mentioned as being useful?

    ReplyDelete
  15. Brent212,

    Didn't see the reference to the standard library in the task description, but I used std::accumulate().

    ReplyDelete
  16. From the task description, I concluded that an empty vector (C++) was always in equilibrium (just like a vector with only 1 element) since for any index, the number of elements before or after is zero, so they're sums are equal (0).

    Also, the concept that an empty container is in equilibrium "feels" right. So my check was if vector.size()>1 before using the algorithm, i.e. all vectors with a size of 0 or 1 are in equilibrium.

    ReplyDelete
  17. Surely its not about a vector/array being 'in equilibrium', its about the existence of a position P that satisfies the problem's conditions. For an array of size 0, this is false because of the condition: 0 <= P < N. No positions exist in an empty array and certainly no positions that are < N!

    ReplyDelete
  18. Anybody got a solution to the disc intersections problem that is < O(n^2)? I failed the tests on scalability.

    Here was my attempt:


    class Solution {

    int number_of_disc_intersections ( int[]A )
    {

    int count = 0;

    for(int i=0; i= j - A[j])
    {
    count++;
    }

    if(count > 10000000)
    return -1;
    }

    }

    return count;


    }
    }

    ReplyDelete
  19. The PS test, lends itself to using a hash table, this means its hard to produce a solution in C in the time scale required (both writing and execution). Has anyone managed to do this?

    I noticed the question did not state, what to do with an out of bounds data set.

    This was my solution, it had a speed up but not a good enough one it seems.

    int ps ( int A[], int n ) {
    if (n<1 || n>1000000)
    return -1;

    int count;
    int count2;

    int test[1000000];
    int test_total=0;
    int pos=0;

    for (count=0;count<n;count++)
    {
    int found=0;
    for (count2=0; count2<test_total; ++count2)
    if (test[count2]==A[count])
    {
    found=1;
    continue;
    }

    if (!found)
    {
    pos=count;
    test[test_total++]=A[count];

    }
    }
    return pos;
    }

    ReplyDelete
  20. Python 100% score:

    def equi ( A ):
    ''''N = len(A)
    ''''total = sum(A)
    ''''lefts = 0
    ''''for p, value in enumerate(A):
    ''''''''partial = total - value
    ''''''''if partial % 2 == 0 and lefts == (partial / 2) and 0 <= p < N:
    ''''''''''''return p
    ''''''''lefts += value
    ''''return -1

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. Another Python 100% one:

      def equi(A):
      ''''if A:
      ''''''''n=len(A)
      ''''''''if n>1:
      ''''''''''''s1=0
      ''''''''''''s2=sum(A)
      ''''''''''''for i,e in enumerate(A):
      ''''''''''''''''if s1==(s2-e):
      ''''''''''''''''''''''''return i
      ''''''''''''''''s1+=e
      ''''''''''''''''s2-=e
      ''''''''''''return -1
      ''''''''else:
      ''''''''''''return 0
      ''''return -1

      Longer to write but I think quicker to execute

      Delete
  21. Perl Solution:

    sub equi {
    my (@A)=@_;
    my $length = (scalar @A) -1;
    my $total_sum = 0;
    $total_sum += $_ foreach @A;
    my $left_sum = 0;
    for( my $i = 0 ; $i <= $length ; $i++ ){
    my $right_sum = $total_sum - $left_sum - $A[$i];
    return $i if $left_sum == $right_sum;
    $left_sum += $A[$i];
    }
    return -1;
    }

    ReplyDelete
    Replies
    1. sub solution {
      my (@A)=@_;
      my @B = 0; $B [$_ + 01] = $B [$_] + $A [$_] for 0 .. @A - 01;
      return (grep { $B [$_] == $B [-01] - $B [$_ + 01] } 0 .. @A - 01) [0] // -01;
      }

      Delete
  22. PHP Solution 100/100 with O(n)

    function equi($arr) {
    $p = -1;
    if( !isset($arr) || count($arr) < 1) return $p;
    else $sum = $arr[0];
    $sum2 = 0;

    $count = count($arr);
    if(1 == $count) return 0;

    for ($i = 2; $i < $count; $i++) $sum2 += $arr[$i];

    // Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N-1.
    if ( ($sum2 + $arr[1]) == 0) return 0;
    else if( ( ($sum2 + $arr[0] + $arr[1]) - $arr[$count - 1] ) == 0) return $p = $count - 1;
    else if( $sum == $sum2) return 1;

    for ( $k = 2; $k < $count; $k++) {
    $sum += $arr[ $k - 1 ];
    $sum2 -= $arr[ $k ];

    if ( $sum == $sum2 ) return $k;
    }

    return $p;
    }


    Cheers,
    Vishnu
    http://vishnu-agarwal.blogspot.com

    ReplyDelete
  23. This comment has been removed by the author.

    ReplyDelete
  24. I am evaluating Codility from the point of view of a hiring manager. While I fully agree with the concept of pre-interview testing, some experimenting with your system has lead me to believe that a fully automated testing system has very little value, and that any hiring decisions based on it are highly suspect.

    Pasted here are two solutions to EQUI in Java. The first scored 100, which, according to your FAQ, is a "high-end programmer" score; the second scored 69, which you describe as a "rather poor result". However, the two solutions are exactly similar except for one minor mistake in the exit condition of the last for-loop, which caused the application to fail some of the tests.

    I do not believe that most humans evaluating each of these programs would believe that such a mistake was enough to differentiate their respective authors to any degree, and I especially doubt that anyone would think that this mistake was enough to distinguish “high-end” from “rather poor”.




    // score 100
    class Solution {
    public int equi ( int[] A )
    {
    int length = A.length;
    long sumF = 0;
    long sumR = 0;
    long[] F = new long[length];
    long[] R = new long[length];
    for(int i = 0; i < length; i++)
    {
    sumF += A[i];
    F[i] = sumF;
    }
    for(int i = length -1; i >= 0; i--)
    {
    sumR += A[i];
    R[i] = sumR;
    }
    for(int i = 0; i < length; i++)
    {
    long pre;
    if(i == 0)
    pre = 0;
    else
    pre = F[i-1];
    long post;
    if(i == length -1)
    post = 0;
    else
    post = R[i+1];
    if(pre == post)
    return i;
    }
    return -1;
    }
    }

    // score 69
    class Solution {
    public int equi ( int[] A )
    {
    int length = A.length;
    long sumF = 0;
    long sumR = 0;
    long[] F = new long[length];
    long[] R = new long[length];
    for(int i = 0; i < length; i++)
    {
    sumF += A[i];
    F[i] = sumF;
    }
    for(int i = length -1; i >= 0; i--)
    {
    sumR += A[i];
    R[i] = sumR;
    }
    // note the exit condition
    for(int i = 0; i < length -1; i++)
    {
    long pre;
    if(i == 0)
    pre = 0;
    else
    pre = F[i-1];
    long post;
    if(i == length -1)
    post = 0;
    else
    post = R[i+1];
    if(pre == post)
    return i;
    }
    return -1;
    }
    }

    ReplyDelete
  25. public int equi(int[] A) {
    if (A.length == 0) return -1;

    long[] sum = new long[A.length];
    sum[0] = A[0];
    for (int i = 1; i < A.length; i++) {
    sum[i] = sum[i - 1] + A[i];
    }

    for (int i = 0; i < A.length; i++) {
    if ((sum[i] - A[i]) == sum[A.length - 1] - sum[i]) {
    return i;
    }
    }

    return -1;
    }

    ReplyDelete
  26. int equi(int[] A) {
    long sum = 0, leftsum = 0;
    int i, l = A.length;
    for (i = 0; i < l; i++) {
    sum += A[i];
    }
    for (i = 0; i < l; i++) {
    sum -= A[i];
    if (leftsum == sum) {
    return i;
    }
    leftsum += A[i];
    }
    return -1;
    }

    ReplyDelete
  27. I got this which got a 94 on the tests, but i had to try it twice... first one was miserable

    int equi(int[] A)
    {
    int i = 0;
    long sumA = 0;
    long sumB = 0;
    for (i = 1; i < A.length; i++)
    {
    sumB += (long)A[i];
    }
    if (sumA == sumB)
    return 0;
    for(i = 1; i < A.length; i++)
    {
    sumB -= (long)A[i];
    sumA += (long)A[i-1];
    if (sumA == sumB)
    {
    return i;
    break;
    }

    }
    return -1;
    }

    }

    ReplyDelete
  28. double lsum= 0;
    double rsum= 0;
    for(int i =1; i < A.Length; i++)
    {

    lsum= lsum+ A[i-1];
    for (int j = i + 1; j < A.Length; j++)
    {
    rsum= rsum+ A[j];
    }


    if (lsum== rsum)
    {
    return i;
    }
    lsum= 0;
    }

    return -1;

    ReplyDelete
  29. A functional approach using C#

    using System;
    // you can also use other imports, for example:
    using System.Collections.Generic;
    using System.Linq;

    class Solution {
    public int equi ( int[] A ) {

    if (A.Length == 0)
    {
    return -1;
    }

    if (A.Length == 1)
    {
    return 0;
    }

    long accum = 0;
    List before = A.ToList().ConvertAll(intt => (long) intt);
    before = before.ConvertAll(index => {
    accum = index + accum;
    return accum;
    }
    );

    accum = 0;
    List after = A.ToList().ConvertAll(intt => (long)intt);
    after.Reverse();
    after = after.ConvertAll(index => {
    accum = index + accum;
    return accum;
    }
    );

    long allButLast = before[A.Length - 2];
    long allButFirst = after[A.Length - 2];
    if (allButLast == 0)
    return A.Length - 1;
    if (allButFirst == 0)
    return 0;

    for (int i = 0; i < A.Length; i++)
    {
    int afterIndex = A.Length - (i + 1);
    if (before[i] == after[afterIndex])
    return i;
    }
    before.TakeWhile((sum, i) => sum != after[i]);
    if (before.Count == A.Length)
    return -1;
    else
    return before.Count - 1;


    }
    }

    ReplyDelete
  30. This comment has been removed by the author.

    ReplyDelete
  31. Finally graduated from 50 % to 100 % in two attempts. To be honest I don't think this is an apt platform to test a developer's capability.

    ReplyDelete
  32. This comment has been removed by the author.

    ReplyDelete
  33. I've read a little here(http://rosettacode.org/wiki/Equilibrium_index) and came out with this for PHP:

    function equi ( $A ) {

    $left = array_sum($A);
    $right = 0;

    foreach($A as $key => $val) {

    $right += $val;

    if($left == $right) return $key;

    $left -= $val;


    }

    return -1;


    }

    ReplyDelete
  34. Score 100 - C#

    using System;

    class Solution {
    public int equi ( int[] A ) {

    long[] LeftToRight = new long[A.Length];
    long[] RightToLeft = new long[A.Length];
    int l=A.Length;

    for(int i=0; i<A.Length; i++)
    {
    if (i==0)
    {
    LeftToRight[i]=A[i];
    RightToLeft[l-1]= A[l-1];
    }
    else
    {
    LeftToRight[i]=LeftToRight[i-1]+A[i];
    RightToLeft[l-1]= RightToLeft[l]+A[l-1];
    }
    l--;
    }

    for (int i=0; i < A.Length; i++)
    {
    if (LeftToRight[i] == RightToLeft[i])
    {
    return i;
    }
    }
    return -1;
    }
    }

    ReplyDelete
  35. This comment has been removed by the author.

    ReplyDelete
  36. Score:100 VB.Net
    dim i,j,lsum,rsum as long
    sum=0
    for i=0 to ubound(A)
    sum=sum+a(i)
    next
    lsum=0
    for i=0 to ubound(A)
    rsum=sum-lsum-a(i)
    if (lsum=rsum) then
    equi=i
    exit function
    end if
    if (i=ubound(a)) then
    if (lsum=0) then
    equi=ubound(a)
    exit function
    end if
    end if
    if (i=0) then
    if (rsum=0) then
    equi=0
    exit function
    end if
    end if
    lsum=lsum+a(i)
    next
    equi=-1

    ReplyDelete
  37. PHP 100/100
    function equi ( $A ) {
    $count = count($A);
    $count_a = 0;
    $count_b = array_sum($A);
    for ($i=0;$i<$count;$i++) {
    $count_a += $A[$i];
    if ($count_a == $count_b) {
    return $i;
    }
    $count_b -= $A[$i];
    }
    return -1;
    }

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  38. PHP
    function equi ( $a) {
    $sum = 0;
    $leftSum = 0;

    for ($i=0;$i<count($a);$i++){
    $leftSum += $a[$i];
    }

    for ($i=0;$i<count($a);$i++){
    if ($sum==$leftSum-$a[$i]) return $i;
    $sum+=$a[$i];
    $leftSum-=$a[$i];
    }
    return -1;

    }

    ReplyDelete
  39. Good Morning, i've tried the demo test in Objective-C, in the proposed code the tester provides an NSMutableArray as argument for the Equi function. An NSMutableArray is a container of objects and NSInteger that is a simple typedef of int base type), cannot be an element of the array. A valid element type could be an NSNumber instance.
    Actually it's not possible to retrieve the elements from the array. I'm in trouble because i need to do a te as a candidate submitted on Codility but if the Objective-C is not implemented correctly i can't do the test properly.

    ReplyDelete
  40. Nobody post a javascript solution, so here is mine:

    function equi ( A ) {
    var count = A.length,
    counter = [0,0],
    equis = [];
    while(count--){
    counter[1] += A[count];
    }
    count = A.length;
    while(count--) {
    counter[0] += A[count];
    if (counter[0] == counter[1]) {
    equis.push(count);
    }
    counter[1] -= A[count];
    }
    return (equis.length)?equis:-1;
    }

    It should return all the equilibrium indexs in case exist more than one.

    ReplyDelete
  41. Your Objective C Compiler is not working, Here is my objective C solution that works just fine in xCode with no warnings or errors. This is a go back and do it again gents, or at the very least warn people your compiler doesn't work for iOS ObjectiveC.
    Regards

    @interface BDAViewController //: UIViewController your coding doesn't recognize #import


    -(int)equi:(NSMutableArray *) A;
    @end



    @implementation BDAViewController

    -(int)equi:(NSMutableArray *) A{
    int outPut = 0;
    int leftSum = 0;
    int rightSum = 0;
    int sumI = [[A valueForKeyPath:@"@sum.self"] intValue];
    NSLog(@"sumITest: %d", sumI);
    for (int i = 0;i<[A count];i++) {//NSNumber *tempNum in A
    rightSum = sumI - leftSum - [[A objectAtIndex:i] intValue];
    if(leftSum == rightSum) return i;

    leftSum += [[A objectAtIndex:i] intValue];
    }

    return outPut;
    }


    Solution verification...
    Compiler output:
    In file included from user.m:30:
    func.m: In function '-[BDAViewController equi:]':
    func.m:19: warning: 'NSMutableArray' may not respond to '-valueForKeyPath:'
    func.m:19: warning: (Messages without a matching method signature
    func.m:19: warning: will be assumed to return 'id' and accept
    func.m:19: warning: '...' as arguments.)
    func.m:21: error: 'for' loop initial declarations are only allowed in C99 mode
    func.m:21: note: use option -std=c99 or -std=gnu99 to compile your code
    user.m: At top level:
    user.m:135: warning: '@end' missing in implementation context

    Verification detected some errors.

    ReplyDelete
  42. public static void main(String[] args) {
    long time = System.nanoTime();
    long[] arg = {1, 55, 23453452L, 65435345434L, 354353452L, 454354356L, 245345345345L, 5, 6, 12, 45};

    int leftIndex = 0,
    rightIndex = arg.length - 1,
    leftSum = 0,
    rightSum = 0;

    while (leftIndex != rightIndex) {

    if (leftSum <= rightSum) {
    leftSum += arg[leftIndex++];
    } else {
    rightSum += arg[rightIndex--];
    }

    }

    System.out.println("leftSum: " + leftSum + "\n" + "rightSum: " + rightSum + "\n" + "leftIndex: " + leftIndex + "\n" + "rightIndex: " + rightIndex);

    long end = System.nanoTime();
    System.out.println(end-time);
    }

    Runs in 0.227 milliseconds. Is that good? I don't know O notation. But it seems to process huge numbers correctly so I'll leave it alone..

    ReplyDelete
  43. second optimum solution given for O(n),
    breaks for: int[] sample = {-7,1,5,2,-4,3,0,7};

    ReplyDelete
  44. I did it this way in Java...
    public int equi(int[] A){
    int left=0,right=0;
    int j=A.length-1;
    for(int i=0;i<A.length;i++){
    left+=A[i];
    right+=A[j];
    if(i==j)
    if(left==right) return i;
    j--;
    }
    return -1;
    }

    ReplyDelete
  45. ruby 100/100
    def equi(a)
      sum = 0
      all_sum = a.inject(:+)
      a.each_with_index do |el, i|
        all_sum -= el
        return i if sum == all_sum
        sum += el
      end
      -1
    end

    ReplyDelete
  46. Another ruby solution:

    class Test
      def equi(a)
        return -1 if a.size == 0
        index_size = a.size - 1
        (1..index_size).each do |index_right|
          tmp_right = 0.0
          tmp_left = 0.0
          a.slice(0, index_right).each{|ai| tmp_right += ai }
          a.slice(index_right + 1, index_size).each{|ai| tmp_left += ai }
          return index_right if tmp_right == tmp_left
        end
        return -1
      end

    a = [-7, 1, 5, 2, -4, 3, 0]
    b = [-7, 2, 5, 2, -4, 4, 0]
    c = [1, 0, 1]
    d = [2, -2, 1]
    e = [2, 2, 2, 2, 4, 8]

    test = Test.new

    puts "::#{test.equi(a)}"
    puts "::#{test.equi(b)}"
    puts "::#{test.equi(c)}"
    puts "::#{test.equi(d)}"
    puts "::#{test.equi(e)}"
    end

    ReplyDelete
  47. A cleaner C# solution than the one in the example (IMO):

    [code]
    long sum = 0;

    for (int pos = 0; pos < A.Length; pos++)
    sum += A[pos];

    long left_sum = 0, right_sum = sum;
    for (int pos = 0; pos < A.Length; pos++) {
    right_sum -= A[pos];

    if (left_sum == right_sum)
    return pos;

    left_sum += A[pos];
    }

    return -1;
    [/code]

    ReplyDelete
    Replies
    1. I think this is the simplest and most elegant solution.

      Delete
  48. function equi ( $A ) {

    $first_part_sum = 0;
    $second_part_sum = array_sum($A) - $A[0];

    foreach ($A AS $k=>$v) {
    if ($first_part_sum == $second_part_sum) {
    return $k;
    break;
    }
    if ($k+1 == count($A)) break;
    $first_part_sum += $v;
    $second_part_sum -= $A[$k+1];
    }

    return -1;
    }

    ReplyDelete
  49. //This Java code gives 100 score to me :)

    // you can also use imports, for example:
    // import java.math.*;
    class Solution {
    public int equi(int[] A) {
    int len = A.length;
    long sum = 0, sum2 = 0;
    int i;
    int result = -1;//no equilibrium
    for (i = 0; i < len; i++) {
    sum += (long)A[i];
    }
    for (i = 0; i < len; i++) {
    if (2 * sum2 + (long)A[i] == sum) {
    // System.out.println(i);
    result = i;
    break;
    }
    sum2 += (long)A[i];
    }
    return result;
    }
    }

    ReplyDelete
  50. why the original soution's return value is -1 ? Isn't it suppose to return the equilibrium index?

    ReplyDelete
  51. Javascript solution:

    function equi ( A ) {

    var n = A.length;

    if (n == 0) return -1;

    var sum = 0;

    for (var i=0; i<n; i++) sum+= A[i];

    var sum_left = 0;

    for (var i=0; i<n; i++) {

    var sum_right = sum - sum_left - A[i];

    if (sum_left == sum_right) return i;

    sum_left += A[i];

    }

    return -1;

    }

    ReplyDelete
  52. This comment has been removed by the author.

    ReplyDelete
  53. Does the equilibrium at the position 0 exists. What should we consider sum of left side of 0th position? This is not mentioned in the requirement of the problem but test cases consider this cases.

    ReplyDelete
  54. PHP score: 100 of 100:
    function equi($array)
    {
    if (1 > count($array)) {
    return -1;
    }
    $fullSum = .0;
    reset($array);
    do {
    $fullSum += (float) current($array);
    } while (false !== next($array));
    $currentSum = .0;
    reset($array);
    do {
    $arrVal = (float) current($array);
    $fullSum -= $arrVal;
    if ($currentSum == $fullSum) {
    return key($array);
    }
    $currentSum += $arrVal;
    } while (false !== next($array));
    return -1;
    }

    ReplyDelete
  55. There is my JS version, pretty much the same as some other posted. However I'm kind of maniac and will never omit the curly brace.

    function equi ( A ) {
    var lSum = 0, rSum = 0, l = A.length;
    for(var i=0; i<l; i++){
    rSum += A[i];
    }
    for(var i=0; i<l; i++){
    rSum -= A[i];

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

    ReplyDelete
  56. C - score: 100 of 100

    int ps ( int A[], int N ) {
    unsigned char hash[(N+7)/8];
    int i = 0;
    int res = 0;

    memset(hash, 0, sizeof(hash));

    for(i = 0; i < N; i++)
    {
    int offset = A[i] / 8;
    unsigned char flag = 1;

    flag <<= (A[i] - (offset * 8));

    if (hash[offset] & flag)
    continue;

    hash[offset] |= flag;
    res = i;
    }

    return res;
    }

    ReplyDelete
  57. Test doesn't seem very relevant to real world things I do in python.

    ReplyDelete
  58. This comment has been removed by the author.

    ReplyDelete
  59. This comment has been removed by the author.

    ReplyDelete
  60. The question description and part of the solution description are inadequate. The wording is important, especially when describing a math problem which was not present in this article. Here is an explanation:

    Point#1:
    --------
    Description says:

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

    Confusion/question:
    - which lower index ?
    - which higher index ?

    A better and more specific description would be:

    "The equilibrium index of a sequence is an index such that the sum of elements at its lower indexes is equal to the sum of elements at its higher indexes."

    Point#2:
    --------

    Description says:
    "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) "

    Confusion/question:
    - What zero elements? We can clearly see that there are six elements i.e. element one A[0], element two A[1], element three A[2], element four A[3], element five A[4] and element six A[5]

    A more specific and appropriate description would be:
    "6th element is also an equilibrium index, because the sum of elements at its lower indexes is zero, i.e., A[0] + A[1] + A[2] + A[3] + A[4] + A[5]=0>>"


    This is math and algorithm, man. Please try to be more specific.

    ReplyDelete
    Replies
    1. I agree, I too got confused initially and then assumed first half and second half.
      I only checked if the mid position is the equi index and didn't check if n(A[6]) = n(A[0]+...+A[5]) because i got confused.

      Ur explanation made this clearer.

      Delete
  61. could anyone please make in Pascal and send to me? I'm juuh_lhp@hotmail.com, thank you

    ReplyDelete
    Replies
    1. [Pascal] Is it possible to get more than 75 points? Did anybody pass tests 3-6?

      Delete
  62. This comment has been removed by the author.

    ReplyDelete
  63. I have this code, but i could not published. Is a C# code:
    public int Solution(int[] A)
    {
    int c1 = 0;
    int c2 = 0;
    c1 = getConditionOne(A);
    c2 = getConditionTwo(A);

    if (c1 != -1 && c2 != -1)
    {
    return c1;
    }
    else if(c1!=-1 && c2==-1)
    {
    return c1;
    }
    else if (c1 == -1 && c2 != -1)
    {
    return c2;
    }
    else
    return -1;
    }

    private int getArrayLen(int[] A)
    {
    return A.Length;
    }

    private int getConditionOne(int[] A)
    {
    //lower and higher indexes
    int len = getArrayLen(A);
    len--;
    int iHalf = len/2;
    int sum1 = 0;
    int sum2 = 0;

    for (int i = 0; i < iHalf; i++)
    {
    sum1 = sum1 + A[i];
    }
    for (int j = iHalf+1; j <= len; j++)
    {
    sum2 = sum2 + A[j];
    }
    if (sum1 == sum2)
    return iHalf;
    else
    return -1;
    }
    private int getConditionTwo(int[] A)
    {
    //sum of elements at its lower indexes
    int len = getArrayLen(A);
    len--;
    int sum1 = 0;
    for (int i = 0; i <= len; i++)
    {
    sum1 = sum1 + A[i];
    }

    if (sum1 == 0)
    return len;
    else
    return -1;
    }

    ReplyDelete
  64. I think this should work in Java!!

    public static int Solution (long [] arr){

    long lsum=0;


    if (arr.length==0){
    return 0;
    }

    for (long i=1;i<arr.length;i++){

    lsum = lsum + arr[(int) (i-1)];

    long rsum=0;

    for (long j=i+1; j<arr.length; j++){

    rsum = rsum + arr[(int) j];
    }

    if (lsum==rsum){
    return (int) i;

    }

    }
    return -1;


    }

    ReplyDelete
    Replies
    1. This might work however the complexity seems to be O(n2) - n square due to nesting loops. O(n) is required.

      Kindly review my code too. I am sure it can be optimized :)

      Delete
  65. Below is my messy code - took 33 minutes and the demo test was 30...
    I am checking if the array has even or odd number of items and then fixing the EquiIndex.


    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace EquilibriumIndex
    {
    class Program
    {
    static void Main(string[] args)
    {
    int[] testArray = { 2,-7, 1, 5, 2, -4, 3, 0 ,2};//new int[7];
    Console.Write(solution(testArray, testArray.Length));
    Console.ReadLine();
    }


    static int solution(int[] A, int N)
    {
    long sumArrayFirstHalf = 0, sumArraySecHalf = 0;
    int p = 0;
    if (N % 2 == 0)
    {


    for (int i = 0; i < N / 2; i++)
    {
    sumArrayFirstHalf += A[i];
    }

    for (int i = N / 2; i < N; i++)
    {
    sumArraySecHalf += A[i];
    }

    if (sumArrayFirstHalf == sumArraySecHalf)
    {
    return (N / 2);
    }

    else
    return -1;
    }

    else
    {
    for (int i = 0; i <= ((N + 1) / 2) - 2; i++)
    {
    sumArrayFirstHalf += A[i];
    }

    for (int i = ((N + 1) / 2); i < N; i++)
    {
    sumArraySecHalf += A[i];
    }

    if (sumArrayFirstHalf == sumArraySecHalf)
    {
    return (((N + 1) / 2) - 2);
    }

    else
    return -1;
    }
    }
    }

    }

    ReplyDelete
  66. Guys, your C++ compiler is bro-ken.

    ::std ::plus < long long > const a_plus;

    error: uninitialized const 'a_plus'

    This error is bogus because plus has a constructor:

    ::std ::plus < long long > const a_plus (0);

    /usr/include/c++/4.4/bits/stl_function.h:136:
    note: candidates are: std::plus::plus()

    That looks like g++ 4.4. How many years ago was that current?

    ReplyDelete
  67. Here is the STL way:

    #include <numeric>

    template < class V, class C >
    /*
    Overrides the declared value type;
    needed because the specification of partial_sum depends on it, which is as weird as can be.
    */
    struct ovvt : public C
    {
    public: typedef V value_type; public: ovvt (C const & c) : C (c) { }
    };

    int solution(const vector &A) {
    // write your code here...
    typedef ovvt < long long, vector < int > ::const_iterator > ovvt_ll;
    int const A1 [] = /* data for the failing test */ { 0, 2147483648, 2147483648 };
    vector < int > const A2 (A); // (A1, A1 + 03);
    typedef vector < long long > t_B; t_B B;
    ovvt_ll const I [02] = { A2 .begin (), A2 .end () };
    B .reserve (A2 .size () + 01); B .push_back (0); partial_sum (* I, I [01], back_inserter (B));
    for (t_B ::const_iterator p ((B) .begin ()); p < B .end () - 01; ++ p)
    if (* p == B .back () - p [01]) return p - B .begin (); return -01;
    return ! accumulate (A2 .begin (), A2 .end (), 0) && B .back (); // test overflow
    }

    ReplyDelete
  68. A Scala solution, which makes use of scanLeft to store the results of the partial sums. Then it's easy to rip through and just index into those partial sums to find equilibrium without having to do any more adding up. I think it works out nicely and is a good example for showing off some Scala niceties. If you don't already know Scala however it might not make much sense :-)

    def solution(a: Array[Int]): Int = {
    // Partial sums are Longs to avoid Int overflow.
    val sums = a.scanLeft(0L)(_ + _).tail

    def equilibrium(index: Int) = leftSum(index) == rightSum(index)
    def leftSum(index: Int) = if (index == 0) 0 else sums(index - 1)
    def rightSum(index: Int) = sums.last - sums(index)

    (0 until a.length) find (equilibrium(_)) getOrElse(-1)
    }

    ReplyDelete
  69. I had submitted a Scala solution like:

    def solution(a: Array[Int]): Int = {
    (1 to a.length-1).toList.map(p =>
    if (a.splitAt(p)._1.reduceLeft(_+_) == a.splitAt(p)._2.reduceLeft(_+_))
    return p)

    -1
    }

    It passed for some test samples, but for others it wasn't quite right or the computation took longer than expected.

    Anyway, it was a good exercise at the end and I had fun doing it!

    ReplyDelete
  70. My linear time/constant space solution, using an input array:

    public int solution(int[] A) {
    int N = A.length;
    for(int i = 0; i< N;i++) {
    A[i] += 1; // to be able to mark negative numbers as owned by prefix subarray
    }
    int P = 0;
    for(int i = 0; i< N;i++) {
    if (A[Math.abs(A[i]) - 1] > 0) {
    P = i;
    A[Math.abs(A[i]) - 1] *= -1; // mark number as owned
    }
    }
    return P;
    }

    ReplyDelete
    Replies
    1. It solution of PrefixSet of course =)

      Delete
    2. Did you get full score for this? What about Tiem complexity

      Delete
  71. A one liner python solution using generator expression. Brief enough to fit my head and is guarnteed to perform well under pypy when executed against a very large lists.

    list(i for i in xrange(len(A)) if sum(A[:i]) == sum(A[i:]))

    Here is a copy from my shell ...

    >>> A = range(7)
    >>> A[0]=-7;A[1]=1;A[2]=5;A[3]=2;A[4]=-4;A[5]=3;A[6]=0
    >>> A
    [-7, 1, 5, 2, -4, 3, 0]
    >>> list(i for i in xrange(len(A)) if sum(A[:i]) == sum(A[i:]))
    [0, 6]

    ReplyDelete
    Replies
    1. should be [3, 6]

      try: list(i for i in xrange(len(A)) if sum(A[:i+1]) == sum(A[i:]))

      cool but, it sums the high end repeatedly

      Delete
  72. Has anybody noticed the example data is in error?
    A[0] + A[1] + A[2] = -1
    A[4] + A[5] + A[6] = 1

    ReplyDelete
  73. An objective- C solution

    int solution(NSMutableArray *A) {
    // write your code here...
    int n = [A count];
    if (n==0) return -1;
    long long sum = 0;
    int i;
    for(i=0;i<n;i++) sum+= [[A objectAtIndex:i] longLongValue];

    long long sum_left = 0;
    for(i=0;i<n;i++) {
    long long sum_right = sum - sum_left - [[A objectAtIndex:i] longLongValue];
    if (sum_left == sum_right) return i;
    sum_left += [[A objectAtIndex:i] longLongValue];
    }
    return -1;

    }

    ReplyDelete
  74. 100pts JavaScript solution:

    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; }
    Lsum += n;
    });
    return eq;
    }

    ReplyDelete
    Replies
    1. I have a question, this must be evaluated to 1?? [-3,2,3]

      Delete
  75. The first solution is O((n^2) * 2) and the second of O(n * 2). Neither one is correct according to the problem parameters.

    ReplyDelete
  76. public static int solution(int[] A) {

    int pivot=0,ans=-1;

    for(int i=0;i<A.length;i++)
    {
    pivot++;

    if(sumArray(A,0,pivot-1)==sumArray(A,pivot+1,A.length-1))
    {
    ans=pivot;
    break;
    }
    else
    ans=-1;
    // break;
    }
    return ans;


    }
    public static int sumArray(int a[],int start,int end)
    {
    int sum=0;
    for(int i=start;i<=end;i++)
    {
    sum=sum+a[i];
    }
    return sum;
    }

    ReplyDelete
  77. Interestingly, Codility's C compiler complains if you use declarations inside of the for clause - says that only is allowed for C99. Fine. But then the proposed solution needs (!) long long type, which was introduced in C99. That's ugly.

    ReplyDelete
  78. Hi this is my solution for java.

    class Solution {
    public int solution(int[] A) {
    int eqIndex=-1;

    long[] bottomUp=new long[A.length];
    long[] topDown=new long[A.length];

    int j=A.length-1;
    for(int i=0;i0){
    topDown[i]=topDown[i-1]+A[i-1];
    bottomUp[j]=bottomUp[j+1]+A[j+1];
    }

    if(i>=A.length/2 && topDown[i]==bottomUp[i]) return i;
    if(i>=A.length/2 && bottomUp[j]==topDown[j]) return j;
    j--;

    }

    return eqIndex;

    }
    }

    ReplyDelete
  79. This might sound a bit intestinal but the spec says return ANY eq, yet proposed solutions returns only and only 1st eq, it would never return 6 as per example above, which fails the of spec. (and would fail a unit test) Also c# compiler has bug, where it fails to correctly identify scope of the variable; Suggestion change spec to ask return ANY FIRST encountered eq;

    ReplyDelete
  80. Hi mates, its enormous piece of writing on the topic of cultureand entirely defined, keep it up
    all the time.

    Feel free to surf to my website ... backlinks
    pyramid (cheapbacklinksforyou.blogspot.com)

    ReplyDelete
  81. I love your blog.. very nice colors & theme. Did
    you design this website yourself or did you hire someone to do
    it for you? Plz answer back as I'm looking to
    construct my own blog and would like to know where u got this from.
    thanks a lot

    Feel free to visit my homepage ... crohn disease

    ReplyDelete
  82. It's enormous that you are getting ideas from this paragraph as well as from our dialogue made at
    this place.

    my web blog :: http://xrumerbacklinksservice.blogspot.com

    ReplyDelete
  83. Guys, can somebody help me, please? Here is my solution for php: http://pastebin.com/eu0Szh9R

    I got wrong answers in "extreme_large_numbers", "extreme_negative_numbers" and "overflow_tests2" tests. But how is this possible in php-language?

    Also, during the test I checked it on "[ 2147483647, 2147483647, 2147483647]" and Codility really reported wrong answer, but my local php returned correct one.

    ReplyDelete
  84. Ruby Solution. Got O(N).

    l = a.count

    return -1 if l == 0

    s = [a[0]]
    (1..l-1).each {|i| s[i] = s[i-1] + a[i] }

    return 0 if s[l-1] - a[0] == 0
    return l-1 if l > 1 && s[l-2] == 0

    (1..l-2).each do |i|
    return i if s[l-1] - s[i] == s[i-1]
    end

    return -1

    ReplyDelete
  85. PHP 100/100

    function solution($A)
    {

    $flag=0;
    $rightSum=0;

    for($i=0;$i<count($A)-1;$i++)
    {
    $rightSum = $rightSum + $A[$i];
    }
    $leftSum=0;

    for($i=0;$i<count($A)-1;$i++)
    {
    $rightSum = $rightSum -$A[$i];
    $leftSum = $leftSum+$A[$i];

    $eq=0;
    if($rightSum == $leftSum)
    {
    $eq=$i+1;
    $flag++;
    break;
    }
    }
    if($flag==0)
    {
    return -1;
    }
    return $eq;

    }

    ReplyDelete
  86. JAVA 100/100
    public class Solution {

    public int solution(int[] A) {
    // write your code in Java SE 7
    int i;
    long total = sum(A);

    if(A == null||A.length == 0){
    return -1;
    }

    long left = 0;
    long right = total - left - A[0];


    if(total - A[A.length -1] == 0){
    return A.length -1;
    }
    for(i = 0; i < A.length - 1; i++){

    if(left == right){
    return i;
    }

    left = left + A[i];
    right = total - left - A [i+1];

    }

    return -1;
    }


    public long sum(int[] A){
    long result = 0;
    for(int t: A){
    result = result + t;
    }
    return result;

    }
    }

    ReplyDelete
  87. Did anyone noticed the so-called complexity O(N) is actually O(2N)?
    One O(N) is when you sum all elements.
    Another O(N) is when testing for equality.

    ReplyDelete
  88. class Equi

      def self.find(a)
        return -1 if !a.is_a?(Array) || a.size ==0
        (1..a.size-1).each { |index|
          return index if right(a, index+1) == left(a, index-1)
        }
        return -1
      end

      def self.left(a, index)
        add( a.slice(0, index+1) )
      end

      def self.right(a, index)
        add( a.slice(index, a.size-1) )
      end

      def self.add(a, sum=0)
        a.each_with_index { |val, idx|
          sum += val
        }
        sum
      end

    end

    # should return -1
    a = nil
    b = "chicken"
    c = []
    d = [3]
    e = [1, 2, 3, 4, 5, 6]

    puts "For #{a.inspect}: #{Equi.find(a)}"
    puts "For #{b.inspect}: #{Equi.find(b)}"
    puts "For #{c.inspect}: #{Equi.find(c)}"
    puts "For #{d.inspect}: #{Equi.find(d)}"
    puts "For #{e.inspect}: #{Equi.find(e)}"

    # should return equilibrium index
    f = [-7, 1, 5, 2, -4, 3, 0]
    g = [-7, 2, 5, 2, -4, 4, 0]
    h = [1, 0, 1]
    i = [2, -2, 1]
    j = [2, 2, 2, 2, 4, 8]

    puts "For #{f.inspect}: #{Equi.find(f)}"
    puts "For #{g.inspect}: #{Equi.find(g)}"
    puts "For #{h.inspect}: #{Equi.find(h)}"
    puts "For #{i.inspect}: #{Equi.find(i)}"
    puts "For #{j.inspect}: #{Equi.find(j)}"

    ReplyDelete
  89. This is my solution in python:

    #########################################

    #!/bin/python

    def solution(mylist):

    suma=sum(mylist)
    N=len(mylist)
    izq=0

    if N == 0: return -1;

    for P in xrange(N):
    der=suma-izq-mylist[P]
    if izq == der:
    return P
    break;
    izq=izq+mylist[P]

    return -1

    ############# Example Array ############

    mylist=[-7,1,5,2,-4,3,0];

    var=solution(mylist);

    ReplyDelete
  90. Java Solution :


    public static int solution(int[] A) {
    // write your code in Java SE 7

    int N = A.length;
    int P = -1;

    long preI = 0;
    long postI = 0;
    for(int x = 0; x< N; x++)
    {
    postI += A[x];
    }
    for(int i = 0; i < N; i++)
    {
    if(preI == (postI-A[i]))
    return i;

    preI += A[i];
    postI -=A[i];

    }

    return P;
    }

    ReplyDelete
  91. def solution(a)
    __left_sum = 0
    __right_sum = a.inject(:+)
    __(0...a.length).each do |i|
    ____left_sum += a[i-1] if i > 0
    ____right_sum += a[i]
    ____return i if left_sum == right_sum
    __end
    __-1
    end

    O(n)

    ReplyDelete
  92. @Bogdan Neacsu:
    "Did anyone noticed the so-called complexity O(N) is actually O(2N)?
    One O(N) is when you sum all elements.
    Another O(N) is when testing for equality"

    Constants (as well as lower-order terms) disappear in big-O notation. O(2N) and O(N) denote the same class of functions.

    ReplyDelete
  93. The solution in C++ would be inherently more complicated (and more robust). In the C++ version you are given just a vector in your function parameters, which has the number of elements stored as a size_t data type. This type is defined by the architecture, as is the type long long. If you say long long is 64-bits, and size_t is also 64-bits, you can still get overflow on long long if you have a large enough vector.

    This would make security programmers cry.

    ReplyDelete
  94. Hi, am I cheating if I use Linq? In that case I believe that is: O(N). Am I wrong?

    public static int Solution(int[] array)
    {
    return EquilibriumIndex(array, 0);
    }

    static int EquilibriumIndex(int[] array, int P)
    {
    int result = -1;

    if (array.Length != P)
    {
    var s1 = array.Take(P).Sum();
    var s2 = array.Skip(P + 1).Sum();
    if (s1 == s2)
    result = P;
    else { result = EquilibriumIndex(array, ++P); }
    }
    return result;
    }

    ReplyDelete
  95. My solution

    function solution($A) {
    $indexes = array();
    $leftSide = 0;
    $rightSide = array_sum($A);
    $i = 0;
    do {
    $leftSide += $A[$i];
    if ($i > 0 && $i < (count($A) + 1) && $leftSide == -$rightSide) {
    return $i;
    }
    $rightSide -= $A[$i];

    $i++;
    } while ($i < count($A));

    return -1;
    }

    ReplyDelete
  96. This gives a 100% score for Python


    def solution(A):

    if len(A) == 0:
    return -1

    result = []
    sum_before = 0
    sum_after = sum(A[0:])


    sum_after -= A[0]

    if sum_before == sum_after:
    result.append(0)
    for i in xrange(1,len(A)):
    sum_before += A[i-1]
    sum_after -= A[i]

    if sum_before == sum_after:
    result.append(i)

    if not(result):
    return -1
    else:
    return result[0]

    ReplyDelete
  97. Perfect score for my threaded solution counting from both sides at once:

    class Solution {

    public int solution(int[] A) {
    // corner case 1 - null or empty
    if (A==null || A.length == 0) return -1;
    // corner case 2 - 1 elem
    if (A.length == 1) return 0;

    // calc total - will fit into long
    long total = 0;
    for (int i=0; i= 0 && pos < a.length; pos+=inc) {
    posval = a[pos];
    sum1-=posval;
    if (sum1==sum2) {
    found=this;
    break;
    }
    sum2+=posval;
    }
    }
    }

    ReplyDelete