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

Java | 18,021 |

C# | 8,105 |

PHP | 6,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]=03 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 if0<= kandsum(A[0..(k-1)])=sum(A[(k+1)..(n-1)]). Assume the sum of zero elements is equal to zero.

Write a functionint 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:

Using this solution, you can obtain a perfect score:

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(n*^{2}) - it fails on large input values (for example if the input array contains values like MIN/MAX_INT) due to the arithmetic overflows

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:

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.

ReplyDeletepublic 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;

}

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

DeleteThis is a 100 points solution for java:

Deletepublic 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;

}

You are running twice over this array, you can do it better!

DeleteTry 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;

}

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

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

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

DeleteThis 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;

}

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.

Deleteint 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;

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDelete# Python solution

ReplyDeletedef 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

This comment has been removed by the author.

DeleteThis comment has been removed by the author.

DeleteThis comment has been removed by the author.

Deletedef equi(A):

Delete____for i in range(1,len(A)):

________if sum(A[0:i]) == sum(A[i+1:len(A)]):

____________return i

____return -1

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.

DeleteWhat is the correct solution for Equi([0,0,0]) ?

ReplyDelete#PYTHON#

ReplyDelete#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

def equi(A):

ReplyDelete````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

@Chris: Return one of {0, 1, 2}.

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

ReplyDelete// Solved @Mangatur

ReplyDeleteusing 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)

Hi Bartosz,

ReplyDeleteI use C# for solution in sample test.

Above is the code you can verify.

Best Regards,

Duane Aritonang

www.ArtDuane.com

Python solution in O(n)

ReplyDeletedef 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

Python solution in O(n),

ReplyDeletedef 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

Perfect Score 100 / 100 with JAVA O(n)

ReplyDeleteclass 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;

}

}

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

ReplyDeleteBrent212,

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

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

ReplyDeleteAlso, 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.

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!

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

ReplyDeleteHere 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;

}

}

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?

ReplyDeleteI 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;

}

Python 100% score:

ReplyDeletedef 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

This comment has been removed by the author.

DeleteAnother Python 100% one:

Deletedef 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

Perl Solution:

ReplyDeletesub 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;

}

sub solution {

Deletemy (@A)=@_;

my @B = 0; $B [$_ + 01] = $B [$_] + $A [$_] for 0 .. @A - 01;

return (grep { $B [$_] == $B [-01] - $B [$_ + 01] } 0 .. @A - 01) [0] // -01;

}

PHP Solution 100/100 with O(n)

ReplyDeletefunction 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

This comment has been removed by the author.

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

ReplyDeletePasted 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;

}

}

public int equi(int[] A) {

ReplyDeleteif (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;

}

int equi(int[] A) {

ReplyDeletelong 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;

}

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

ReplyDeleteint 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;

}

}

double lsum= 0;

ReplyDeletedouble 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;

A functional approach using C#

ReplyDeleteusing 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;

}

}

This comment has been removed by the author.

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

ReplyDeleteThis comment has been removed by the author.

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

ReplyDeletefunction equi ( $A ) {

$left = array_sum($A);

$right = 0;

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

$right += $val;

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

$left -= $val;

}

return -1;

}

Score 100 - C#

ReplyDeleteusing 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;

}

}

This comment has been removed by the author.

ReplyDeleteScore:100 VB.Net

ReplyDeletedim 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

you forgot to declare sum as long

Delete:)

PHP 100/100

ReplyDeletefunction 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;

}

This comment has been removed by the author.

DeletePHP

ReplyDeletefunction 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;

}

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.

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

Nobody post a javascript solution, so here is mine:

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

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.

ReplyDeleteRegards

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

public static void main(String[] args) {

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

second optimum solution given for O(n),

ReplyDeletebreaks for: int[] sample = {-7,1,5,2,-4,3,0,7};

I did it this way in Java...

ReplyDeletepublic 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;

}

ruby 100/100

ReplyDeletedef 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

Another ruby solution:

ReplyDeleteclass 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

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

ReplyDelete[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]

I think this is the simplest and most elegant solution.

Deletefunction equi ( $A ) {

ReplyDelete$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;

}

//This Java code gives 100 score to me :)

ReplyDelete// 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;

}

}

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

ReplyDeleteJavascript solution:

ReplyDeletefunction 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;

}

This comment has been removed by the author.

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

ReplyDeletePHP score: 100 of 100:

ReplyDeletefunction 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;

}

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.

ReplyDeletefunction 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;

}

C - score: 100 of 100

ReplyDeleteint 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;

}

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

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThe 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:

ReplyDeletePoint#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.

I agree, I too got confused initially and then assumed first half and second half.

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

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

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

DeleteThis comment has been removed by the author.

ReplyDeleteI have this code, but i could not published. Is a C# code:

ReplyDeletepublic 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;

}

I think this should work in Java!!

ReplyDeletepublic 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;

}

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

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

Below is my messy code - took 33 minutes and the demo test was 30...

ReplyDeleteI 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;

}

}

}

}

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

ReplyDelete::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?

Here is the STL way:

ReplyDelete#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

}

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 :-)

ReplyDeletedef 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)

}

I had submitted a Scala solution like:

ReplyDeletedef 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!

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

ReplyDeletepublic 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;

}

It solution of PrefixSet of course =)

DeleteDid you get full score for this? What about Tiem complexity

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

ReplyDeletelist(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]

should be [3, 6]

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

cool but, it sums the high end repeatedly

Has anybody noticed the example data is in error?

ReplyDeleteA[0] + A[1] + A[2] = -1

A[4] + A[5] + A[6] = 1

Dude, since when is 3-4 = 1 ?

DeleteAn objective- C solution

ReplyDeleteint 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;

}

100pts JavaScript solution:

ReplyDeletefunction 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;

}

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

ReplyDeletepublic static int solution(int[] A) {

ReplyDeleteint 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;

}

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.

ReplyDeleteHi this is my solution for java.

ReplyDeleteclass 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;

}

}

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;

ReplyDeleteHi mates, its enormous piece of writing on the topic of cultureand entirely defined, keep it up

ReplyDeleteall the time.

Feel free to surf to my website ... backlinks

pyramid (cheapbacklinksforyou.blogspot.com)

I love your blog.. very nice colors & theme. Did

ReplyDeleteyou 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

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

ReplyDeletethis place.

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

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

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

Ruby Solution. Got O(N).

ReplyDeletel = 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

PHP 100/100

ReplyDeletefunction 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;

}

JAVA 100/100

ReplyDeletepublic 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;

}

}

Did anyone noticed the so-called complexity O(N) is actually O(2N)?

ReplyDeleteOne O(N) is when you sum all elements.

Another O(N) is when testing for equality.