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;

I don't think this works for this case {-7,-1,-5,-2, 4, -3,0}

Deleteshould return 1 since P[0] == P[1]+P[2]+P[3]+P[4]+P[5]+P[6] but it returns -1...

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

Deleteint length = A.Length ;

Deleteint leftSum=0;

int rightSum = 0;

if(length<1)

{

return -1;

}

for(int i=0; i < length; i++)

{

int index = i;

for (int j= 0; j<=index; j++)

{

leftSum+=A[j];

}

for (int k= index+1; k<length; k++)

{

rightSum+=A[k];

}

if(leftSum==rightSum)

{

return i;

}

}

return length;

I did this for a java solution :

Deleteclass Solution {

public int solution(int[] A) {

int result = -1;

long sum = Arrays.stream(A).sum();

long left = 0;

long right = 0;

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

int j = A[i];

left += j;

right = sum - left;

if (left - j == right && (0 <= i && i < A.length)) {

result = i;

break;

}

}

return result;

}

}

but only got Correctness 65% and Performance 100%

Why only 65% ??

Arrays.stream(A).sum() sums the array as ints, which overflows. If you add the elements as longs, the solution should score 100%.

DeleteAhh of cause : this gave 100%

Deleteclass Solution {

public int solution(int[] a) {

int result = -1;

long[] b = IntStream.range(0, a.length).mapToLong(i -> a[i]).toArray();

long sum = Arrays.stream(b).sum();

long left = 0;

long right = 0;

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

long j = b[i];

left += j;

right = sum - left;

if (left - j == right && (0 <= i && i < b.length)) {

//System.out.println("index " + i);

result = i;

break;

}

}

return result;

}

}

I do not know why codility says some test fails for my solution but i have tested some especially the large_long_sequence_of_ones with exactly the same indices an values and it works. If someone can hint me on what is wrong. In order to save time, i traversed the array from both sides together to find the needed index.

Deleteimport java.util.Arrays;

import java.util.stream.IntStream;

class Solution {

public int solution(int[] A) {

// write your code in Java SE 8

long[] arr = IntStream.range(0, A.length).mapToLong(i -> A[i]).toArray();

long totalSum = Arrays.stream(arr).sum();

long count = totalSum;

long upperSum = 0;

long lowerSum = 0;

for( int i = arr.length - 1; i >= 0; i-- ){

if( totalSum - arr[i] == upperSum || count - arr[arr.length - 1 - i] == lowerSum ){

return i;

}

totalSum -= arr[i];

upperSum += arr[i];

lowerSum += arr[arr.length - 1 - i];

count -= arr[arr.length - 1 - i];

}

return -1;

}

}

Hi David,

DeleteIt looks like the "return" is wrong: if "count - arr[arr.length - 1 - i] == lowerSum" is true, then you need to return "arr.length - 1 - i", not "i".

I would suggest writing simpler code to avoid mistakes like this - traversing the array from both sides is a micro-optimization that does not improve the time complexity.

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.

DeletePerformance 100%, correctness 56% only tho..

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

ReplyDelete0,1 or 2

Delete#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().

...which will overflow badly if you're not careful about your init value type.

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

// you can also use imports, for example:

Delete#import

// you can use printf for debugging purposes, e.g.

// printf("this is a debug message\n");

int solution(NSMutableArray *A) {

// write your code in Objective-C 2.0

for(int i = 1;i<[A count];i++)

{

int firstSum = 0, secondSum = 0;

int j = 0,k = 0;

for(j = 0 ; j < i ; j++)

{

firstSum += [[A objectAtIndex:j] intValue];

}

NSLog(@"%d",firstSum);

for(k = i+1 ; k < [A count] ; k++)

{

secondSum +=[[A objectAtIndex:k] intValue];

}

NSLog(@"%d",secondSum);

if(firstSum == secondSum)

return i;

}

return -1;

}

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;

}

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

DeleteVerified that this achieves 100pts, but how can that be if it returns 1 for [-1,-1,-1] while the rules say "An equilibrium index of this array is any integer P such that 0 ≤ P < N" (quoted from original description) or "The integer k is an equilibrium index [...]] if and only if 0<= k" (quoted from the description on this page)?

Deleteforget what I just wrote, it's Friday afternoon ^^

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

class Equi

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

This is my solution in python:

ReplyDelete#########################################

#!/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);

Java Solution :

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

}

def solution(a)

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

@Bogdan Neacsu:

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

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.

ReplyDeleteThis would make security programmers cry.

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

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

}

My solution

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

}

This gives a 100% score for Python

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

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

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

}

}

}

**100% Score : Javascript**

ReplyDeletefunction solution(A) {

// write your code in JavaScript (ECMA-262, 5th edition)

var p=0;

var index=0;

var leftSum=0;

var rightSum=0;

var totalSum=0;

var N = A.length;

var last_minimum=100000;

if(A.length == 2)

return (Math.abs(A[0]-A[1]));

if(A.length == 1)

return (Math.abs(A[0]));

for(index=0; index < N; index++)

totalSum = totalSum + A[index];

for(p=1; p <= N-1; p++){

leftSum += A[p - 1];

rightSum = totalSum - leftSum;

current_min = Math.abs(leftSum - rightSum);

last_minimum = current_min < last_minimum ? current_min : last_minimum;

if (last_minimum === 0)

break;

}

return last_minimum;

}

**100% Score in C Program**

ReplyDeleteint solution(int A[], int N) {

long p;

long index;

long leftSum;

long rightSum;

long totalSum=0;

long last_minimum=100000;

long current_min;

if(N==2) return abs(A[0]-A[1]);

if(N==1) return abs(A[0]);

for(index=0; index < N; index++)

totalSum = totalSum + A[index];

leftSum = 0; rightSum = 0;

for (p = 1; p <= N-1; p++) {

leftSum += A[p - 1];

rightSum = totalSum - leftSum;

current_min = abs((long)(leftSum - rightSum));

last_minimum = current_min < last_minimum ? current_min : last_minimum;

if (last_minimum == 0)

break;

}

return last_minimum;

}

int abs(int n) {

return (n >= 0) ? n : (-(n));

}

int solution(int A[], int N);

ReplyDeleteint solution(int A[], int N) {

// write your code in C90

int i =0,j=0;

int left_sum = 0,right_sum =0;

for(i=1;i<N;i++)

{

left_sum =0;

right_sum =0;

for(j=0;j<i;j++)

{

left_sum = left_sum +A[j];

}

for(j=i+1;j<N;j++)

{

right_sum = right_sum +A[j];

}

if(!(left_sum-right_sum))

return(i);

}

if(i == N)

return(-1);

}

As a django developer - I cannot see how this tests anything relevant.

ReplyDeleteThis line:

ReplyDeleteif (n==0) return -1;

wasn't necessary, because n is greater than 0, according to the task.

I'm wondering if the question, as stated in the demo task, could be made a dyslexic friendly?

ReplyDeleteIt would have been more accessible if it had said something like:

"write a function that finds the equilibrium element of an integer array. The 'equilibrium element' is the one where, the sum of itself with all the previous elements, is the same as the sum of the following elements"

Whereas, the phrasing I got was:

"A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.

A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1]…" (and so on).

This meant that, being dyslexic and unable to sequence, I was timed out of the task because the way you'd phrased the question was unreadable to me.

With 20+ years of programming experience, I have found that my dyslexia enables me to have a better leverage of the tools of my trade and to problem solve intuitively, both of which are valuable contributions to the teams I've worked in. Good programming is not about mathematical & algebraic ability, but problem solving, logic, and attention to detail. However, it does mean I 'fail' algebra-based "aptitude" tests.

I think that rephrasing the question would be a good idea, as discriminating against people who are not mathematically fluent, is not serving your clients well. Their loss.

It seems to me that 'Equil' is a poor choice of an example to cite when testing programmers in C#, Java, and Javascript (and all Visual Studio managed languages).

In the 'requirements', the programmer has to be aware of scalability and cost; whilst this might count for the rare low level database and graphics coding tasks, this is not appropriate to the majority of programming roles in todays world, where it is far more important to have *readable*, maintainable and extend-able code.

These high scoring examples fail on all these qualities.

Never-the-less, I have written two solutions in C#, one of which I hope to post separately.

""" Author Mukhtiar Gill

ReplyDeleteDate November 2014

"""

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

master = [-1,3,-4,5,1,-6,2,1]

pot = []

def solution(A):

if sum( master[ len(pot) + 1: ] ) == sum(pot):

print "Equilibrium index at", len(pot)

pot.append(A.pop(0))

if len(A) > 0:

solution(A[0:])

solution(A)

int solution(int A[], int N) {

ReplyDeleteint lsum=0,rsum=0,i,evalue=-1;

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

rsum=rsum+A[i];

}

for(i=1;i<N;i++){

lsum=lsum+A[i-1];

rsum=rsum-(A[i]+lsum);

if(lsum==rsum){

evalue=i;

break;

}

}

return evalue;

}

Is that OK?

ReplyDeletepublic int solution(int[] A)

{

try

{

int intLength = A.Length;

long lngRSide = 0;

long lngLSide = 0;

for (int p = 0; p < intLength; p++)

{

// RSide

for (int j = intLength - 1; j > p; j--)

{

lngRSide = lngRSide + A[j];

}

// LSide

for (int k = 0; k < p; k++)

{

lngLSide = lngLSide + A[k];

}

if (lngRSide == lngLSide)

return p;

lngRSide = 0;

lngLSide = 0;

}

return -1;

}

catch

{

return -1;

}

}

Thanks.

Hi,

Deletefirst of all, you can check the solution yourself by taking our demo test. If you want to see an assessment, it's here: https://codility.com/demo/results/demoGYX6H7-PCY/. Sorry for the lack of indentation, it looks like our blog engine ate it...

As you can see, your solution returns the right value, but it's too slow - the challenge is to solve the problem in O(N). Also, the "catch" block should not be necessary, as your code doesn't do anything that would throw an exception. I hope this helps!

How is that?

ReplyDeletetry

{

int intLength = A.Length;

long lngLSide = 0;

long lngRSide = 0;

long lngSum = 0;

for (int p = 0; p < intLength; p++)

lngSum = lngSum + A[p];

for (int p = 0; p < intLength; p++)

{

lngRSide = lngSum - (A[p] + lngLSide);

if (lngLSide == lngRSide)

return p;

lngLSide = lngLSide + A[p];

}

return -1;

}

catch

{

return -1;

}

Thanks.

This is a correct, O(N) solution. The "try/catch" is unnecessary, though.

DeleteIs it just me or most of the answers (if not all of them) are wrong?

ReplyDeleteI don't mean to be picky but according to the problem description:

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

So it should return ANY of the indexes found, NOT JUST THE FIRST, so for the following array:

-1,3,-4,5,1,-6,2,1

The correct solutions could be 1, 3 or 7. You would sometimes get a 1, others a 3 and others a 7.... all solutions so far always return a 1 which is the first solution and not ANY. This means that all answers, even those provided by codility, are wrong and that there is a flaw in the check answers engine. It should run a certain number of times to validate effectively that the answer is getting ANY of the indexes and not always the first.

This would be a more appropriate solution (in PHP):

function solution($A) {

$return = -1;

if(is_array($A) && (count($A) > 0)) {

$probableValues = array();

$leftSum = 0;

$totalSum = 0;

$rightSum = $totalSum;

for($index = 0; $index < count($A); $index++){

$totalSum += $A[$index];

}

for($index = 0; $index < count($A); $index++){

$rightSum = $totalSum - ($leftSum + $A[$index]);

if($leftSum == $rightSum){

$probableValues[] = $index;

}

$leftSum += $A[$index];

}

$return = (count($probableValues) > 0)?($probableValues[mt_rand(0,(count($probableValues)-1))]):-1;

}

return $return;

}

Kerry Hood is right, you are doing a question in a fancy way, asked for a result in a very vague way and thus all your answers can be considered wrong because of that.

If you were asking for only one result you could rephrase the question as one of the following:

"[...] given a sequence, returns the smallest equilibrium index or -1 if no equilibrium index exists. Assume that the sequence may be very long." - This would imply the first from left to right

or

"[...] given a sequence, returns the biggest equilibrium index or -1 if no equilibrium index exists. Assume that the sequence may be very long." - This would imply the first from right to left

I'm afraid your understanding of "any" is rather idiosyncratic. If you are asked to "pick any colour", you are not forced to rethink the decision each time or think about all possible colors and choose a random one. It means you can pick the color freely.

DeletePlease note this blog post is relatively old, we have improved the description since: http://codility.com/tasks/equi.

I see your point, you are talking about a developers freedom to choose which index he will return while I was talking about the function's return values. Got it :D Thanks!

ReplyDeleteHere is a simple solution I implemented in Python and got 100% Score:

ReplyDeletedef solution(A):

t_s = sum(A)

f_h = 0

for index in range(len(A)):

s_h = t_s - f_h - A[index]

if f_h == s_h:

return index

f_h += A[index]

return -1

You explained this C++ code really nicely thank you so much for your efforts.

ReplyDeleteC++ in Urdu

C# - 100%

ReplyDeletepublic int solution(int[] A)

{

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

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

long firstHalfSum = 0;

long secondHalfSum = A.Skip(1).Select(i => (long)i).Sum();

if (secondHalfSum == 0) return 0;

for (var x = 0; x < A.Length - 2; x++)

{

firstHalfSum += A[x];

secondHalfSum = secondHalfSum - A[x + 1];

if (firstHalfSum == secondHalfSum) return x + 1;

}

if (firstHalfSum + A[A.Length - 2] == 0) return A.Length - 1;

return -1;

}

C# - Cleaner version

ReplyDeletepublic int solution(int[] A)

{

if (A.Length <= 1) return A.Length == 0 ? -1 : 0;

long firstHalfSum = 0;

var secondHalfSum = A.Skip(1).Select(i => (long)i).Sum();

if (secondHalfSum == 0) return 0;

for (var x = 0; x < A.Length - 2; x++)

{

firstHalfSum += A[x];

secondHalfSum = secondHalfSum - A[x + 1];

if (firstHalfSum == secondHalfSum) return x + 1;

}

if (firstHalfSum + A[A.Length - 2] == 0) return A.Length - 1;

return -1;

}

I wasted 10 minutes on this question because the scala compiler is broken, it couldn't understand for comprehension syntax. I think I'd better submit my answers in C, because it sounds like their other backends are pretty shit.

ReplyDeleteval leftSums = A.scanLeft(0)(_ + _).dropRight(1)

ReplyDeleteval rightSums = A.scanRight(0)(_ + _).drop(1)

val results = (leftSums,rightSums,(0 to leftSums.length)).zipped.collect{ case (a,b,i) if (a == b) => i }

if (results.isEmpty) -1 else results.head

This type of assessments maybe measure some analytical skills but all of them are useless in a real work environment. This is more like going back to college and taking again the course of analysis of algorithm.

ReplyDeleteHere is a Scala one... Testing using Random number generation but without negative numbers ;-)

ReplyDeleteI could test quickly for various cases by changing the end to various numbers.

import scala.annotation.tailrec

/**

* Created by atul on 24/4/15.

*/

object Solution extends App {

@tailrec

def solution(l: List[Int], leftSum: Int, totalSum: Int, ind: Int): Int = l match {

case Nil => ind

case x :: tail => if (leftSum == totalSum - x)

ind

else

solution(tail, leftSum + x, totalSum - x, ind + 1)

}

// val l = Array(-1, 3, -4, 5, 1, -6, 2, 1).toList

// val l = Array(5, 3, 8, 4, 2, 1, 1).toList

// val l = Array(-1, 3, -4, 5, 1, 5, -1, -1).toList

val end = 1080

val to = 55

val l1 = (for (i <- 1 to end) yield scala.util.Random.nextInt(to)).toList

val l = l1 ++ List(to) ++ l1

val sum = l.reduceLeft(_ + _)

val result = solution(l, 0, sum, 0)

println(result)

}

function solution(A) {

ReplyDeletefor(var k = 0; k < A.length; k++) {

var lsum = 0,

rsum = 0;

for(var j = 0; j < k; j++) lsum += A[j];

for(var i = k+1; i < A.length; i++) rsum += A[i];

if(lsum == rsum) return k;

}

return -1;

}

Fine work!

function solution(A) {

ReplyDeletefor(var k = 0; k < A.length; k++) {

var lsum = 0,

rsum = 0;

for(var j = 0; j < k; j++) lsum += A[j];

for(var i = k+1; i < A.length; i++) rsum += A[i];

if(lsum == rsum) return k;

}

return -1;

}

Fine work

If I take all the whitespace out of my answer and replace all my variable names with random garbage I can still get 100%

ReplyDeleteI think our definitions of 'programming skill' differ somewhat.

Hi Andy,

DeleteThat's true, our software is not sophisticated enough to score on the basis of coding style or readability. These are best reviewed by a human, although we might experiment with automatic assessment in the future...

// for 100% performance and compliance in C++11

ReplyDeleteint solution(vector &A) {

// write your code in C++11

long long sumall = 0;

for(const auto& v : A)

sumall+=v;

long long left=0;

for(int P=0;P<A.size();++P){

if(left == sumall-A[P]-left)

return P;

left+=A[P];

}

return -1;

}

100% Score

ReplyDelete100% Performance

100% Correctness

This is my Code :

public int solution(int[] A) {

int equilibium = -1;

long sum = 0;

for(int i : A)

sum += i;

long lowerIndSum = 0;

long higherIndSum = sum;

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

higherIndSum = higherIndSum - A[i];

if(higherIndSum == lowerIndSum) {

equilibium = i;

break;

}

lowerIndSum = lowerIndSum + A[i];

}

return equilibium;

}

On the demo test I just looked at it says elements of the array can be modified.

ReplyDeleteSo my solution was: to just set all elements to zero and return N-1.

This validated fine but the final score was only 8%. Maybe I didn't understand

the rules of the game?

// you can also use imports, for example:

ReplyDelete// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.

// System.out.println("this is a debug message");

import java.util.Arrays;

class Solution {

public int solution(int[] A) {

int size = A.length;

for(int i = 0; i < size; i++){

if(i == 0 || i == (size-1)){

if(somar(A, i) == 0){

return i;

}

} else {

int[] left = Arrays.copyOfRange(A, 0, i);

int[] right = Arrays.copyOfRange(A, i+1, size);

if(somar(left) == somar(right)){

return i;

}

}

}

return -1;

}

public int somar(int[] A){

int result = 0;

for(int i : A)

result += i;

return result;

}

public int somar(int[] A, int excludedIndex){

int result = this.somar(A);

result -= A[excludedIndex];

return result;

}

}

Hi Juliano,

DeleteUnfortunately this solution is O(N^2) and does not take care of large numbers well.