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 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 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:
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.
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(n2)
- it fails on large input values (for example if the input array contains values like MIN/MAX_INT) due to the arithmetic overflows
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:
Java solution, having said that I am not 100% sure what it's meant to return if the two sides are equal. I just set it to return what the sides are equal to. I haven't tested this properly but it should work for large inputs.
ReplyDeletepublic static int equi(int A[], int k)
{
if(0<=k) {
int sum1 = 0;
int sum2 = 0;
for(int i = 0; i < k; i++) {
sum1 += A[i];
}
for(int i = k+1; i < A.length; i++) {
sum2 += A[i];
}
if(sum1 == sum2) {
return sum1;
}
}
return -1;
}
It won't work with large inputs because u have "int" in type of sum...
DeleteThis is a 100 points solution for java:
Deletepublic int equi( int[] A ) {
long sum = 0;
long leftSum = 0;
for (int i=0;i<A.length;i++){
leftSum += A[i];
}
for (int i=0;i<A.length;i++){
if (sum==leftSum-A[i]) return i;
sum+=A[i];
leftSum-=A[i];
}
return -1;
}
You are running twice over this array, you can do it better!
DeleteTry counting from both sides and always try yo keep the sum of 0, just move where ever is better. Something like this:
int equi(int arr[]) {
int n = arr.length;
if (n <= 0)
return -1;
long sum = arr[0] + arr[n - 1];
for (int leftcount = 0, rightCount = n - 1; leftcount < rightCount - 1;) {
long tmpLeftSum = sum + arr[leftcount + 1];
long tmpRightSum = sum + arr[rightCount - 1];
if(Math.abs(tmpLeftSum) <= Math.abs(tmpRightSum)){
leftcount++;
sum = tmpLeftSum;
}
else{
rightCount--;
sum = tmpRightSum;
}
if(rightCount - leftcount == 1 && sum == 0){
return leftcount + 1;
}
}
return -1;
}
I can't imagine this returns the correct equi. Why deciding on which side to continue summing up (incrementing leftcount or rightCount) based on the current left and right temporary sum? And you overwrite sum all the time o_O
DeleteThe more I look at your code, the more mistakes I find. You shall have a look at the task description once again.
Pablos solution is good, but could it brake if long grows too big. Having a lot of Integer.MAX_VALUE.
DeleteThis would make it a bit safer:
public int equi(int[] A) {
BigDecimal sum = new BigDecimal(0);
BigDecimal leftSum = new BigDecimal(0);
for (int i = 0; i < A.length; i++) {
leftSum=leftSum.add(new BigDecimal(A[i]));
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(leftSum.add(new BigDecimal(-A[i])))==0)
return i;
sum=sum.add(new BigDecimal(A[i]));
leftSum=leftSum.add(new BigDecimal(-A[i]));
}
return -1;
}
This solution achieves 100 score. The fastest way is to perform an initial sum and then just add to the left side and subtract from the right side. That way you only iterate the list twice, achieving O(2n) performance.
Deleteint equilibriumIndex = -1;
int potentialEqIdx = 0;
long lowerSum = 0l;
long upperSum = 0l;
for(int j = potentialEqIdx+1; j < A.length; j++) {
upperSum += A[j];
}
while(potentialEqIdx < A.length) {
if(potentialEqIdx > 0 ) {
lowerSum += A[potentialEqIdx-1];
}
if(potentialEqIdx+1 > 1) {
upperSum = (upperSum - A[potentialEqIdx]);
}
if(lowerSum == upperSum) {
equilibriumIndex = potentialEqIdx;
break;
}
++potentialEqIdx;
}
return equilibriumIndex;
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete# Python solution
ReplyDeletedef equi(A):
````total_sum = sum(A)
````prev, curr = 0, A[0]
````for index in range(1, len(A)):
````````prev += A[index - 1]
````````curr += A[index]
````````if prev + curr == total_sum:
````````````return index
````return -1
This comment has been removed by the author.
DeleteThis comment has been removed by the author.
DeleteThis comment has been removed by the author.
Deletedef equi(A):
Delete____for i in range(1,len(A)):
________if sum(A[0:i]) == sum(A[i+1:len(A)]):
____________return i
____return -1
What is the correct solution for Equi([0,0,0]) ?
ReplyDelete#PYTHON#
ReplyDelete#75% Analysis_Runtime
def equi(A):
````````if A==[]:
`````````````````return -1
````````length=len(A)
````````mid=length//2
````````s=sum(A)
````````if s-A[0]==0:
````````````````return 0
````````if s-A[length-1]==0:
````````````````return length-1
````````for i in range(length)[1:length-1]:
````````````````si=s-A[i]
````````````````if i<mid:
````````````````````````if si==sum(A[:i])*2:
````````````````````````````````return i
````````````````else:
````````````````````````if si==sum(A[i+1:])*2:
````````````````````````````````return i
````````return -1
def equi(A):
ReplyDelete````n = len(A)
````if n == 0:
````````return -1
````total = sum(A)
````lsum = 0
````rsum = total
````for i in range(n):
````````rsum -= A[i]
````````if lsum == rsum:
````````````return i
````````lsum += A[i]
````return -1
@Chris: Return one of {0, 1, 2}.
ReplyDeleteIn c# aditional solution is to work on pointers but the author don't allow to use "unsafe" block
ReplyDelete// Solved @Mangatur
ReplyDeleteusing System;
// you can also use other imports, for example:
// using System.Collections.Generic;
class Solution {
public int equi ( int[] A ) {
long sum = 0;
int i = 0;
for (i = 0; i < A.Length; i++)
{
sum += (long) A[i];
}
long sum_left = 0;
for (i = 0; i < A.Length; i++)
{
long sum_right = sum - sum_left - (long) A[i];
if (sum_left == sum_right)
{
return i;
}
sum_left += (long) A[i];
}
return -1;
}
}
// post @ArtDuane (June 08, 2011)
Hi Bartosz,
ReplyDeleteI use C# for solution in sample test.
Above is the code you can verify.
Best Regards,
Duane Aritonang
www.ArtDuane.com
Python solution in O(n)
ReplyDeletedef equi ( A ):
gtotal = sum(A)
j = gtotal
k = 0
ctr = 0
for i in A:
j = j -i
if j == k: return ctr
k = k + i
ctr += 1
return -1
Python solution in O(n),
ReplyDeletedef equi ( A ):
''''gtotal = sum(A)
''''j = gtotal
''''k = 0
''''ctr = 0
''''for i in A:
''''''j = j -i
''''''if j == k: return ctr
''''''k = k + i
''''''ctr += 1
''''return -1
Perfect Score 100 / 100 with JAVA O(n)
ReplyDeleteclass Solution {
int equi ( int[] A ) {
long sum = 0, leftsum = 0;
int i, l = A.length;
for(i = 0; i < l ; i++){
sum += A[i];
}
for(i = 0; i < l ; i++){
sum -= A[i];
if(leftsum == sum){
return i;
}
leftsum += A[i];
}
return -1;
}
}
So what's that C++ standard library that the task description mentioned as being useful?
ReplyDeleteBrent212,
ReplyDeleteDidn't see the reference to the standard library in the task description, but I used std::accumulate().
From the task description, I concluded that an empty vector (C++) was always in equilibrium (just like a vector with only 1 element) since for any index, the number of elements before or after is zero, so they're sums are equal (0).
ReplyDeleteAlso, the concept that an empty container is in equilibrium "feels" right. So my check was if vector.size()>1 before using the algorithm, i.e. all vectors with a size of 0 or 1 are in equilibrium.
Surely its not about a vector/array being 'in equilibrium', its about the existence of a position P that satisfies the problem's conditions. For an array of size 0, this is false because of the condition: 0 <= P < N. No positions exist in an empty array and certainly no positions that are < N!
ReplyDeleteAnybody got a solution to the disc intersections problem that is < O(n^2)? I failed the tests on scalability.
ReplyDeleteHere was my attempt:
class Solution {
int number_of_disc_intersections ( int[]A )
{
int count = 0;
for(int i=0; i= j - A[j])
{
count++;
}
if(count > 10000000)
return -1;
}
}
return count;
}
}
The PS test, lends itself to using a hash table, this means its hard to produce a solution in C in the time scale required (both writing and execution). Has anyone managed to do this?
ReplyDeleteI noticed the question did not state, what to do with an out of bounds data set.
This was my solution, it had a speed up but not a good enough one it seems.
int ps ( int A[], int n ) {
if (n<1 || n>1000000)
return -1;
int count;
int count2;
int test[1000000];
int test_total=0;
int pos=0;
for (count=0;count<n;count++)
{
int found=0;
for (count2=0; count2<test_total; ++count2)
if (test[count2]==A[count])
{
found=1;
continue;
}
if (!found)
{
pos=count;
test[test_total++]=A[count];
}
}
return pos;
}
Python 100% score:
ReplyDeletedef equi ( A ):
''''N = len(A)
''''total = sum(A)
''''lefts = 0
''''for p, value in enumerate(A):
''''''''partial = total - value
''''''''if partial % 2 == 0 and lefts == (partial / 2) and 0 <= p < N:
''''''''''''return p
''''''''lefts += value
''''return -1
This comment has been removed by the author.
DeleteAnother Python 100% one:
Deletedef equi(A):
''''if A:
''''''''n=len(A)
''''''''if n>1:
''''''''''''s1=0
''''''''''''s2=sum(A)
''''''''''''for i,e in enumerate(A):
''''''''''''''''if s1==(s2-e):
''''''''''''''''''''''''return i
''''''''''''''''s1+=e
''''''''''''''''s2-=e
''''''''''''return -1
''''''''else:
''''''''''''return 0
''''return -1
Longer to write but I think quicker to execute
Perl Solution:
ReplyDeletesub equi {
my (@A)=@_;
my $length = (scalar @A) -1;
my $total_sum = 0;
$total_sum += $_ foreach @A;
my $left_sum = 0;
for( my $i = 0 ; $i <= $length ; $i++ ){
my $right_sum = $total_sum - $left_sum - $A[$i];
return $i if $left_sum == $right_sum;
$left_sum += $A[$i];
}
return -1;
}
PHP Solution 100/100 with O(n)
ReplyDeletefunction equi($arr) {
$p = -1;
if( !isset($arr) || count($arr) < 1) return $p;
else $sum = $arr[0];
$sum2 = 0;
$count = count($arr);
if(1 == $count) return 0;
for ($i = 2; $i < $count; $i++) $sum2 += $arr[$i];
// Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N-1.
if ( ($sum2 + $arr[1]) == 0) return 0;
else if( ( ($sum2 + $arr[0] + $arr[1]) - $arr[$count - 1] ) == 0) return $p = $count - 1;
else if( $sum == $sum2) return 1;
for ( $k = 2; $k < $count; $k++) {
$sum += $arr[ $k - 1 ];
$sum2 -= $arr[ $k ];
if ( $sum == $sum2 ) return $k;
}
return $p;
}
Cheers,
Vishnu
http://vishnu-agarwal.blogspot.com
This comment has been removed by the author.
ReplyDeleteI am evaluating Codility from the point of view of a hiring manager. While I fully agree with the concept of pre-interview testing, some experimenting with your system has lead me to believe that a fully automated testing system has very little value, and that any hiring decisions based on it are highly suspect.
ReplyDeletePasted here are two solutions to EQUI in Java. The first scored 100, which, according to your FAQ, is a "high-end programmer" score; the second scored 69, which you describe as a "rather poor result". However, the two solutions are exactly similar except for one minor mistake in the exit condition of the last for-loop, which caused the application to fail some of the tests.
I do not believe that most humans evaluating each of these programs would believe that such a mistake was enough to differentiate their respective authors to any degree, and I especially doubt that anyone would think that this mistake was enough to distinguish “high-end” from “rather poor”.
// score 100
class Solution {
public int equi ( int[] A )
{
int length = A.length;
long sumF = 0;
long sumR = 0;
long[] F = new long[length];
long[] R = new long[length];
for(int i = 0; i < length; i++)
{
sumF += A[i];
F[i] = sumF;
}
for(int i = length -1; i >= 0; i--)
{
sumR += A[i];
R[i] = sumR;
}
for(int i = 0; i < length; i++)
{
long pre;
if(i == 0)
pre = 0;
else
pre = F[i-1];
long post;
if(i == length -1)
post = 0;
else
post = R[i+1];
if(pre == post)
return i;
}
return -1;
}
}
// score 69
class Solution {
public int equi ( int[] A )
{
int length = A.length;
long sumF = 0;
long sumR = 0;
long[] F = new long[length];
long[] R = new long[length];
for(int i = 0; i < length; i++)
{
sumF += A[i];
F[i] = sumF;
}
for(int i = length -1; i >= 0; i--)
{
sumR += A[i];
R[i] = sumR;
}
// note the exit condition
for(int i = 0; i < length -1; i++)
{
long pre;
if(i == 0)
pre = 0;
else
pre = F[i-1];
long post;
if(i == length -1)
post = 0;
else
post = R[i+1];
if(pre == post)
return i;
}
return -1;
}
}
public int equi(int[] A) {
ReplyDeleteif (A.length == 0) return -1;
long[] sum = new long[A.length];
sum[0] = A[0];
for (int i = 1; i < A.length; i++) {
sum[i] = sum[i - 1] + A[i];
}
for (int i = 0; i < A.length; i++) {
if ((sum[i] - A[i]) == sum[A.length - 1] - sum[i]) {
return i;
}
}
return -1;
}
int equi(int[] A) {
ReplyDeletelong sum = 0, leftsum = 0;
int i, l = A.length;
for (i = 0; i < l; i++) {
sum += A[i];
}
for (i = 0; i < l; i++) {
sum -= A[i];
if (leftsum == sum) {
return i;
}
leftsum += A[i];
}
return -1;
}
I got this which got a 94 on the tests, but i had to try it twice... first one was miserable
ReplyDeleteint equi(int[] A)
{
int i = 0;
long sumA = 0;
long sumB = 0;
for (i = 1; i < A.length; i++)
{
sumB += (long)A[i];
}
if (sumA == sumB)
return 0;
for(i = 1; i < A.length; i++)
{
sumB -= (long)A[i];
sumA += (long)A[i-1];
if (sumA == sumB)
{
return i;
break;
}
}
return -1;
}
}
double lsum= 0;
ReplyDeletedouble rsum= 0;
for(int i =1; i < A.Length; i++)
{
lsum= lsum+ A[i-1];
for (int j = i + 1; j < A.Length; j++)
{
rsum= rsum+ A[j];
}
if (lsum== rsum)
{
return i;
}
lsum= 0;
}
return -1;
A functional approach using C#
ReplyDeleteusing System;
// you can also use other imports, for example:
using System.Collections.Generic;
using System.Linq;
class Solution {
public int equi ( int[] A ) {
if (A.Length == 0)
{
return -1;
}
if (A.Length == 1)
{
return 0;
}
long accum = 0;
List before = A.ToList().ConvertAll(intt => (long) intt);
before = before.ConvertAll(index => {
accum = index + accum;
return accum;
}
);
accum = 0;
List after = A.ToList().ConvertAll(intt => (long)intt);
after.Reverse();
after = after.ConvertAll(index => {
accum = index + accum;
return accum;
}
);
long allButLast = before[A.Length - 2];
long allButFirst = after[A.Length - 2];
if (allButLast == 0)
return A.Length - 1;
if (allButFirst == 0)
return 0;
for (int i = 0; i < A.Length; i++)
{
int afterIndex = A.Length - (i + 1);
if (before[i] == after[afterIndex])
return i;
}
before.TakeWhile((sum, i) => sum != after[i]);
if (before.Count == A.Length)
return -1;
else
return before.Count - 1;
}
}
This comment has been removed by the author.
ReplyDeleteFinally graduated from 50 % to 100 % in two attempts. To be honest I don't think this is an apt platform to test a developer's capability.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteI've read a little here(http://rosettacode.org/wiki/Equilibrium_index) and came out with this for PHP:
ReplyDeletefunction equi ( $A ) {
$left = array_sum($A);
$right = 0;
foreach($A as $key => $val) {
$right += $val;
if($left == $right) return $key;
$left -= $val;
}
return -1;
}
Score 100 - C#
ReplyDeleteusing System;
class Solution {
public int equi ( int[] A ) {
long[] LeftToRight = new long[A.Length];
long[] RightToLeft = new long[A.Length];
int l=A.Length;
for(int i=0; i<A.Length; i++)
{
if (i==0)
{
LeftToRight[i]=A[i];
RightToLeft[l-1]= A[l-1];
}
else
{
LeftToRight[i]=LeftToRight[i-1]+A[i];
RightToLeft[l-1]= RightToLeft[l]+A[l-1];
}
l--;
}
for (int i=0; i < A.Length; i++)
{
if (LeftToRight[i] == RightToLeft[i])
{
return i;
}
}
return -1;
}
}
This comment has been removed by the author.
ReplyDeleteScore:100 VB.Net
ReplyDeletedim i,j,lsum,rsum as long
sum=0
for i=0 to ubound(A)
sum=sum+a(i)
next
lsum=0
for i=0 to ubound(A)
rsum=sum-lsum-a(i)
if (lsum=rsum) then
equi=i
exit function
end if
if (i=ubound(a)) then
if (lsum=0) then
equi=ubound(a)
exit function
end if
end if
if (i=0) then
if (rsum=0) then
equi=0
exit function
end if
end if
lsum=lsum+a(i)
next
equi=-1
you forgot to declare sum as long
Delete:)
PHP 100/100
ReplyDeletefunction equi ( $A ) {
$count = count($A);
$count_a = 0;
$count_b = array_sum($A);
for ($i=0;$i<$count;$i++) {
$count_a += $A[$i];
if ($count_a == $count_b) {
return $i;
}
$count_b -= $A[$i];
}
return -1;
}
This comment has been removed by the author.
DeletePHP
ReplyDeletefunction equi ( $a) {
$sum = 0;
$leftSum = 0;
for ($i=0;$i<count($a);$i++){
$leftSum += $a[$i];
}
for ($i=0;$i<count($a);$i++){
if ($sum==$leftSum-$a[$i]) return $i;
$sum+=$a[$i];
$leftSum-=$a[$i];
}
return -1;
}
Good Morning, i've tried the demo test in Objective-C, in the proposed code the tester provides an NSMutableArray as argument for the Equi function. An NSMutableArray is a container of objects and NSInteger that is a simple typedef of int base type), cannot be an element of the array. A valid element type could be an NSNumber instance.
ReplyDeleteActually it's not possible to retrieve the elements from the array. I'm in trouble because i need to do a te as a candidate submitted on Codility but if the Objective-C is not implemented correctly i can't do the test properly.
Nobody post a javascript solution, so here is mine:
ReplyDeletefunction equi ( A ) {
var count = A.length,
counter = [0,0],
equis = [];
while(count--){
counter[1] += A[count];
}
count = A.length;
while(count--) {
counter[0] += A[count];
if (counter[0] == counter[1]) {
equis.push(count);
}
counter[1] -= A[count];
}
return (equis.length)?equis:-1;
}
It should return all the equilibrium indexs in case exist more than one.
Your Objective C Compiler is not working, Here is my objective C solution that works just fine in xCode with no warnings or errors. This is a go back and do it again gents, or at the very least warn people your compiler doesn't work for iOS ObjectiveC.
ReplyDeleteRegards
@interface BDAViewController //: UIViewController your coding doesn't recognize #import
-(int)equi:(NSMutableArray *) A;
@end
@implementation BDAViewController
-(int)equi:(NSMutableArray *) A{
int outPut = 0;
int leftSum = 0;
int rightSum = 0;
int sumI = [[A valueForKeyPath:@"@sum.self"] intValue];
NSLog(@"sumITest: %d", sumI);
for (int i = 0;i<[A count];i++) {//NSNumber *tempNum in A
rightSum = sumI - leftSum - [[A objectAtIndex:i] intValue];
if(leftSum == rightSum) return i;
leftSum += [[A objectAtIndex:i] intValue];
}
return outPut;
}
Solution verification...
Compiler output:
In file included from user.m:30:
func.m: In function '-[BDAViewController equi:]':
func.m:19: warning: 'NSMutableArray' may not respond to '-valueForKeyPath:'
func.m:19: warning: (Messages without a matching method signature
func.m:19: warning: will be assumed to return 'id' and accept
func.m:19: warning: '...' as arguments.)
func.m:21: error: 'for' loop initial declarations are only allowed in C99 mode
func.m:21: note: use option -std=c99 or -std=gnu99 to compile your code
user.m: At top level:
user.m:135: warning: '@end' missing in implementation context
Verification detected some errors.
public static void main(String[] args) {
ReplyDeletelong time = System.nanoTime();
long[] arg = {1, 55, 23453452L, 65435345434L, 354353452L, 454354356L, 245345345345L, 5, 6, 12, 45};
int leftIndex = 0,
rightIndex = arg.length - 1,
leftSum = 0,
rightSum = 0;
while (leftIndex != rightIndex) {
if (leftSum <= rightSum) {
leftSum += arg[leftIndex++];
} else {
rightSum += arg[rightIndex--];
}
}
System.out.println("leftSum: " + leftSum + "\n" + "rightSum: " + rightSum + "\n" + "leftIndex: " + leftIndex + "\n" + "rightIndex: " + rightIndex);
long end = System.nanoTime();
System.out.println(end-time);
}
Runs in 0.227 milliseconds. Is that good? I don't know O notation. But it seems to process huge numbers correctly so I'll leave it alone..
second optimum solution given for O(n),
ReplyDeletebreaks for: int[] sample = {-7,1,5,2,-4,3,0,7};
I did it this way in Java...
ReplyDeletepublic int equi(int[] A){
int left=0,right=0;
int j=A.length-1;
for(int i=0;i<A.length;i++){
left+=A[i];
right+=A[j];
if(i==j)
if(left==right) return i;
j--;
}
return -1;
}
ruby 100/100
ReplyDeletedef equi(a)
sum = 0
all_sum = a.inject(:+)
a.each_with_index do |el, i|
all_sum -= el
return i if sum == all_sum
sum += el
end
-1
end
Another ruby solution:
ReplyDeleteclass Test
def equi(a)
return -1 if a.size == 0
index_size = a.size - 1
(1..index_size).each do |index_right|
tmp_right = 0.0
tmp_left = 0.0
a.slice(0, index_right).each{|ai| tmp_right += ai }
a.slice(index_right + 1, index_size).each{|ai| tmp_left += ai }
return index_right if tmp_right == tmp_left
end
return -1
end
a = [-7, 1, 5, 2, -4, 3, 0]
b = [-7, 2, 5, 2, -4, 4, 0]
c = [1, 0, 1]
d = [2, -2, 1]
e = [2, 2, 2, 2, 4, 8]
test = Test.new
puts "::#{test.equi(a)}"
puts "::#{test.equi(b)}"
puts "::#{test.equi(c)}"
puts "::#{test.equi(d)}"
puts "::#{test.equi(e)}"
end
A cleaner C# solution than the one in the example (IMO):
ReplyDelete[code]
long sum = 0;
for (int pos = 0; pos < A.Length; pos++)
sum += A[pos];
long left_sum = 0, right_sum = sum;
for (int pos = 0; pos < A.Length; pos++) {
right_sum -= A[pos];
if (left_sum == right_sum)
return pos;
left_sum += A[pos];
}
return -1;
[/code]
function 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.
could anyone please make in Pascal and send to me? I'm juuh_lhp@hotmail.com, thank you
ReplyDeleteThis 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;
}