## Friday, March 25, 2011

One of our most frequently solved tasks is Equi. It is one of our demo problems (freely available without registration). As of today, we have evaluated over 50,000 solutions to this problem.
The most popular language used for solving this problem is Java, though of course C#, PHP and C++ are also very popular:
Programming language Solutions count
Java18,021
C#8,105
PHP6,350
C++6,042
C 4,208
Python 4,151
Ruby 1,915
JavaScript 1,107
Perl 774
Pascal 760
The problem description is very short:
The equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:
A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0
3 is an equilibrium index, because:
A[0]+A[1]+A[2]=A[4]+A[5]+A[6]
6 is also an equilibrium index, because:
A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0
(The sum of zero elements is zero) 7 is not an equilibrium index - because it is not a valid index of sequence A. If you still have doubts, here is a precise definition: The integer k is an equilibrium index of a sequence A[0],A[1]..,A[n-1] if and only if 0<= k and sum(A[0..(k-1)])=sum(A[(k+1)..(n-1)]). Assume the sum of zero elements is equal to zero.

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

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

Using this solution, you can obtain a perfect score:

### What's next?

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

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

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

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

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

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

}

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

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

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

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

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

}
return -1;
}

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

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

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

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

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

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

int equilibriumIndex = -1;
int potentialEqIdx = 0;

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

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

while(potentialEqIdx < A.length) {

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

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

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

}

return equilibriumIndex;

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

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

9. int length = A.Length ;

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

10. I did this for a java solution :

class 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% ??

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

12. Ahh of cause : this gave 100%

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

}
}

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

import 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;
}
}

14. Hi David,

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

2. This comment has been removed by the author.

3. This comment has been removed by the author.

4. # Python solution

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

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

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

````return -1

1. This comment has been removed by the author.

2. This comment has been removed by the author.

3. This comment has been removed by the author.

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

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

6. Performance 100%, correctness 56% only tho..

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

6. #PYTHON#
#75% Analysis_Runtime

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

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

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

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

10. // Solved @Mangatur

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

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

// post @ArtDuane (June 08, 2011)

11. Hi Bartosz,

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

Best Regards,
Duane Aritonang
www.ArtDuane.com

12. Python solution in O(n)

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

13. Python solution in O(n),

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

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

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

16. Brent212,

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

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

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

18. 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!

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

Here was my attempt:

class Solution {

int number_of_disc_intersections ( int[]A )
{

int count = 0;

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

if(count > 10000000)
return -1;
}

}

return count;

}
}

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

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

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

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

int count;
int count2;

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

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

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

}
}
return pos;
}

21. Python 100% score:

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

1. This comment has been removed by the author.

2. Another Python 100% one:

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

Longer to write but I think quicker to execute

22. Perl Solution:

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

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

23. PHP Solution 100/100 with O(n)

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

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

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

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

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

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

return \$p;
}

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

24. This comment has been removed by the author.

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

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

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

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

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

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

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

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

return -1;
}

27. 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;
}

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

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

}
return -1;
}

}

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

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

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

return -1;

30. A functional approach using C#

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

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

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

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

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

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

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

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

}
}

31. This comment has been removed by the author.

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

33. This comment has been removed by the author.

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

function equi ( \$A ) {

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

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

\$right += \$val;

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

\$left -= \$val;

}

return -1;

}

35. Score 100 - C#

using System;

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

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

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

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

36. This comment has been removed by the author.

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

1. you forgot to declare sum as long

:)

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

1. This comment has been removed by the author.

39. PHP
function equi ( \$a) {
\$sum = 0;
\$leftSum = 0;

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

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

}

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

1. // you can also use imports, for example:
#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;
}

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

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

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

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

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

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

@implementation BDAViewController

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

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

return outPut;
}

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

Verification detected some errors.

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

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

while (leftIndex != rightIndex) {

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

}

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

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

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

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

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

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

47. Another ruby solution:

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

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

test = Test.new

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

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

[code]
long sum = 0;

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

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

if (left_sum == right_sum)
return pos;

left_sum += A[pos];
}

return -1;
[/code]

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

49. function equi ( \$A ) {

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

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

return -1;
}

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

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

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

52. Javascript solution:

function equi ( A ) {

var n = A.length;

if (n == 0) return -1;

var sum = 0;

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

var sum_left = 0;

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

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

if (sum_left == sum_right) return i;

sum_left += A[i];

}

return -1;

}

53. This comment has been removed by the author.

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

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

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

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

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

57. C - score: 100 of 100

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

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

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

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

if (hash[offset] & flag)
continue;

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

return res;
}

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

59. This comment has been removed by the author.

60. This comment has been removed by the author.

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

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

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

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

A better and more specific description would be:

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

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

Description says:
"6 is also an equilibrium index, because: A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0 (The sum of zero elements is zero) "

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

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

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

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

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

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

63. This comment has been removed by the author.

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

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

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

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

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

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

65. I think this should work in Java!!

public static int Solution (long [] arr){

long lsum=0;

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

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

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

long rsum=0;

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

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

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

}

}
return -1;

}

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

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

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

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

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

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

}

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

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

error: uninitialized const 'a_plus'

This error is bogus because plus has a constructor:

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

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

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

68. Here is the STL way:

#include <numeric>

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

int solution(const vector &A) {
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
}

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

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

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

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

70. I had submitted a Scala solution like:

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

-1
}

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

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

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

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

1. It solution of PrefixSet of course =)

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

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

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

Here is a copy from my shell ...

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

1. should be [3, 6]

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

cool but, it sums the high end repeatedly

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

1. Dude, since when is 3-4 = 1 ?

74. An objective- C solution

int solution(NSMutableArray *A) {
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;

}

75. 100pts JavaScript solution:

function solution(A) {
var total = (function(a){ var l = a.length, s = 0; while(--l>-1){ s+=a[l] } return s; }(A)),
eq = -1,
l = A.length,
Lsum = 0,
Rsum = 0;
A.forEach(function(n,i){
Rsum = total - Lsum - n;
if(Rsum == Lsum){ eq = i; }
Lsum += n;
});
return eq;
}

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

2. Verified 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)?

3. forget what I just wrote, it's Friday afternoon ^^

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

77. public static int solution(int[] A) {

int pivot=0,ans=-1;

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

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

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

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

79. Hi this is my solution for java.

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

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

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

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

}

return eqIndex;

}
}

80. 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;

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

Feel free to surf to my website ... backlinks

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

Feel free to visit my homepage ... crohn disease

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

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

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

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

85. Ruby Solution. Got O(N).

l = a.count

return -1 if l == 0

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

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

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

return -1

86. PHP 100/100

function solution(\$A)
{

\$flag=0;
\$rightSum=0;

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

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

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

}

87. JAVA 100/100
public class Solution {

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

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

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

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

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

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

}

return -1;
}

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

}
}

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

89. class Equi

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

def self.left(a, index)
end

def self.right(a, index)
end

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

90. This is my solution in python:

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

#!/bin/python

def solution(mylist):

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

if N == 0: return -1;

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

return -1

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

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

var=solution(mylist);

91. Java Solution :

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

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

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

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

}

return P;
}

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

O(n)

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

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

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

This would make security programmers cry.

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

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

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

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

96. My solution

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

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

return -1;
}

97. This gives a 100% score for Python

def solution(A):

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

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

sum_after -= A[0]

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

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

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

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

class Solution {

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

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

99. **100% Score : Javascript**

function 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. **100% Score in C Program**

int 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));
}

101. int solution(int A[], int N);
int 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);

}

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

103. This line:
if (n==0) return -1;
wasn't necessary, because n is greater than 0, according to the task.

104. I'm wondering if the question, as stated in the demo task, could be made a dyslexic friendly?
It 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.

105. """ Author Mukhtiar Gill
Date 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)

106. int solution(int A[], int N) {
int 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;
}

107. Is that OK?

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

1. Hi,
first 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!

108. How is that?

try
{
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.

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

109. Is it just me or most of the answers (if not all of them) are wrong?
I 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

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

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

110. 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!

111. Here is a simple solution I implemented in Python and got 100% Score:

def 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

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

113. C# - 100%

public 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;
}

114. C# - Cleaner version

public 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;
}

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

116. val leftSums = A.scanLeft(0)(_ + _).dropRight(1)
val rightSums = A.scanRight(0)(_ + _).drop(1)
val results = (leftSums,rightSums,(0 to leftSums.length)).zipped.collect{ case (a,b,i) if (a == b) => i }

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

118. Here is a Scala one... Testing using Random number generation but without negative numbers ;-)
I 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)
}

119. function solution(A) {
for(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!

120. function solution(A) {
for(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

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

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

1. Hi Andy,
That'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...

122. // for 100% performance and compliance in C++11
int 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;
}

123. 100% Score
100% 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;
}

124. On the demo test I just looked at it says elements of the array can be modified.
So 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?

125. // you can also use imports, for example:
// 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;
}
}

1. Hi Juliano,
Unfortunately this solution is O(N^2) and does not take care of large numbers well.