Equilibrium index

From Rosetta Code
Jump to: navigation, search
Task
Equilibrium index
You are encouraged to solve this task according to the task description, using any language you may know.

An equilibrium index of a sequence is an index into the sequence such that the sum of elements at lower indices is equal to the sum of elements at higher indices. For example, in a sequence A:

A0 = − 7
A1 = 1
A2 = 5
A3 = 2
A4 = − 4
A5 = 3
A6 = 0

3 is an equilibrium index, because:

A0 + A1 + A2 = A4 + A5 + A6

6 is also an equilibrium index, because:

A0 + A1 + A2 + A3 + A4 + A5 = 0

(sum of zero elements is zero)

7 is not an equilibrium index, because it is not a valid index of sequence A.

Write a function that, given a sequence, returns its equilibrium indices (if any). Assume that the sequence may be very long.

Contents

[edit] Ada

Works with: Ada 2005

Generic solution that returns a Vector of Indices.

equilibrium.ads:

with Ada.Containers.Vectors;
 
generic
type Index_Type is range <>;
type Element_Type is private;
Zero : Element_Type;
with function "+" (Left, Right : Element_Type) return Element_Type is <>;
with function "-" (Left, Right : Element_Type) return Element_Type is <>;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
type Array_Type is private;
with function Element (From : Array_Type; Key : Index_Type) return Element_Type is <>;
package Equilibrium is
package Index_Vectors is new Ada.Containers.Vectors
(Index_Type => Positive, Element_Type => Index_Type);
 
function Get_Indices (From : Array_Type) return Index_Vectors.Vector;
 
end Equilibrium;

equilibrium.adb:

package body Equilibrium is
 
function Get_Indices (From : Array_Type) return Index_Vectors.Vector is
Result : Index_Vectors.Vector;
Right_Sum, Left_Sum : Element_Type := Zero;
begin
for Index in Index_Type'Range loop
Right_Sum := Right_Sum + Element (From, Index);
end loop;
for Index in Index_Type'Range loop
Right_Sum := Right_Sum - Element (From, Index);
if Left_Sum = Right_Sum then
Index_Vectors.Append (Result, Index);
end if;
Left_Sum := Left_Sum + Element (From, Index);
end loop;
return Result;
end Get_Indices;
 
end Equilibrium;

Test program using two different versions, one with vectors and one with arrays:

with Ada.Text_IO;
with Equilibrium;
with Ada.Containers.Vectors;
 
procedure Main is
subtype Index_Type is Positive range 1 .. 7;
package Vectors is new Ada.Containers.Vectors
(Element_Type => Integer, Index_Type => Index_Type);
type Plain_Array is array (Index_Type) of Integer;
function Element (From : Plain_Array; Key : Index_Type) return Integer is
begin
return From (Key);
end Element;
 
package Vector_Equilibrium is new Equilibrium
(Index_Type => Index_Type,
Element_Type => Integer,
Zero => 0,
Array_Type => Vectors.Vector,
Element => Vectors.Element);
package Array_Equilibrium is new Equilibrium
(Index_Type => Index_Type,
Element_Type => Integer,
Zero => 0,
Array_Type => Plain_Array);
 
My_Vector : Vectors.Vector;
My_Array : Plain_Array := (-7, 1, 5, 2, -4, 3, 0);
Vector_Result : Vector_Equilibrium.Index_Vectors.Vector;
Array_Result : Array_Equilibrium.Index_Vectors.Vector :=
Array_Equilibrium.Get_Indices (My_Array);
begin
Vectors.Append (My_Vector, -7);
Vectors.Append (My_Vector, 1);
Vectors.Append (My_Vector, 5);
Vectors.Append (My_Vector, 2);
Vectors.Append (My_Vector, -4);
Vectors.Append (My_Vector, 3);
Vectors.Append (My_Vector, 0);
Vector_Result := Vector_Equilibrium.Get_Indices (My_Vector);
Ada.Text_IO.Put_Line ("Results:");
Ada.Text_IO.Put ("Array: ");
for I in Array_Result.First_Index .. Array_Result.Last_Index loop
Ada.Text_IO.Put (Integer'Image (Array_Equilibrium.Index_Vectors.Element (Array_Result, I)));
end loop;
Ada.Text_IO.New_Line;
Ada.Text_IO.Put ("Vector: ");
for I in Vector_Result.First_Index .. Vector_Result.Last_Index loop
Ada.Text_IO.Put (Integer'Image (Vector_Equilibrium.Index_Vectors.Element (Vector_Result, I)));
end loop;
Ada.Text_IO.New_Line;
end Main;
Output:

(Index_Type is based on 1):

Results:
Array:  4 7
Vector:  4 7

Version that works with Ada 95, too:

Works with: Ada 95
Works with: Ada 2005

equilibrium.adb:

with Ada.Text_IO;
 
procedure Equilibrium is
 
type Integer_Sequence is array (Positive range <>) of Integer;
function Seq_Img (From : Integer_Sequence) return String is
begin
if From'First /= From'Last then
return " " & Integer'Image (From (From'First)) &
Seq_Img (From (From'First + 1 .. From'Last));
else
return " " & Integer'Image (From (From'First));
end if;
end Seq_Img;
 
type Boolean_Sequence is array (Positive range <>) of Boolean;
function Seq_Img (From : Boolean_Sequence) return String is
begin
if From'First > From'Last then
return "";
end if;
if From (From'First) then
return Integer'Image (From'First) &
Seq_Img (From (From'First + 1 .. From'Last));
else
return Seq_Img (From (From'First + 1 .. From'Last));
end if;
end Seq_Img;
 
function Get_Indices (From : Integer_Sequence) return Boolean_Sequence is
Result : Boolean_Sequence (From'Range) := (others => False);
Left_Sum, Right_Sum : Integer := 0;
begin
for Index in From'Range loop
Right_Sum := Right_Sum + From (Index);
end loop;
for Index in From'Range loop
Right_Sum := Right_Sum - From (Index);
Result (Index) := Left_Sum = Right_Sum;
Left_Sum  := Left_Sum + From (Index);
end loop;
return Result;
end Get_Indices;
 
X1 : Integer_Sequence := (-7, 1, 5, 2, -4, 3, 0);
X1_Result : Boolean_Sequence := Get_Indices (X1);
X2 : Integer_Sequence := ( 2, 4, 6);
X2_Result : Boolean_Sequence := Get_Indices (X2);
X3 : Integer_Sequence := ( 2, 9, 2);
X3_Result : Boolean_Sequence := Get_Indices (X3);
X4 : Integer_Sequence := ( 1, -1, 1, -1, 1 ,-1, 1);
X4_Result : Boolean_Sequence := Get_Indices (X4);
 
begin
Ada.Text_IO.Put_Line ("Results:");
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("X1:" & Seq_Img (X1));
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X1_Result));
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("X2:" & Seq_Img (X2));
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X2_Result));
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("X3:" & Seq_Img (X3));
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X3_Result));
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("X4:" & Seq_Img (X4));
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X4_Result));
end Equilibrium;
Output:
Results:

X1: -7  1  5  2 -4  3  0
Eqs: 4 7

X2:  2  4  6
Eqs:

X3:  2  9  2
Eqs: 2

X4:  1 -1  1 -1  1 -1  1
Eqs: 1 2 3 4 5 6 7

[edit] ALGOL 68

Translation of: C
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
MODE YIELDINT = PROC(INT)VOID;
 
PROC gen equilibrium index = ([]INT arr, YIELDINT yield)VOID:
(
INT sum := 0;
FOR i FROM LWB arr TO UPB arr DO
sum +:= arr[i]
OD;
 
INT left:=0, right:=sum;
FOR i FROM LWB arr TO UPB arr DO
right -:= arr[i];
IF left = right THEN yield(i) FI;
left +:= arr[i]
OD
);
 
test:(
[]INT arr = []INT(-7, 1, 5, 2, -4, 3, 0)[@0];
# FOR INT index IN # gen equilibrium index(arr, # ) DO ( #
## (INT index)VOID:
print(index)
# OD # );
print(new line)
)
Output:
         +3         +6

[edit] AutoHotkey

Equilibrium_index(list, BaseIndex=0){
StringSplit, A, list, `,
Loop % A0 {
i := A_Index , Pre := Post := 0
loop, % A0
if (A_Index < i)
Pre += A%A_Index%
else if (A_Index > i)
Post += A%A_Index%
if (Pre = Post)
Res .= (Res?", ":"") i - (BaseIndex?0:1)
}
return Res
}
Examples:
list = -7, 1, 5, 2, -4, 3, 0
MsgBox % Equilibrium_index(list)
Outputs:
3, 6

[edit] BBC BASIC

BBC BASIC's SUM function is useful for this task.

      DIM list(6)
list() = -7, 1, 5, 2, -4, 3, 0
PRINT "Equilibrium indices are " FNequilibrium(list())
END
 
DEF FNequilibrium(l())
LOCAL i%, r, s, e$
s = SUM(l())
FOR i% = 0 TO DIM(l(),1)
IF r = s - r - l(i%) THEN e$ += STR$(i%) + ","
r += l(i%)
NEXT
= LEFT$(e$)

Output:

Equilibrium indices are 3,6

[edit] C

#include <stdio.h>
#include <stdlib.h>
 
int list[] = {-7, 1, 5, 2, -4, 3, 0};
 
int eq_idx(int *a, int len, int **ret)
{
int i, sum, s, cnt;
/* alloc long enough: if we can afford the original list,
* we should be able to afford to this. Beats a potential
* million realloc() calls. Even if memory is a real concern,
* there's no garantee the result is shorter than the input anyway */

cnt = s = sum = 0;
*ret = malloc(sizeof(int) * len);
 
for (i = 0; i < len; i++)
sum += a[i];
 
for (i = 0; i < len; i++) {
if (s * 2 + a[i] == sum) {
(*ret)[cnt] = i;
cnt++;
}
s += a[i];
}
 
/* uncouraged way to use realloc since it can leak memory, for example */
*ret = realloc(*ret, cnt * sizeof(int));
 
return cnt;
}
 
int main()
{
int i, cnt, *idx;
cnt = eq_idx(list, sizeof(list) / sizeof(int), &idx);
 
printf("Found:");
for (i = 0; i < cnt; i++)
printf(" %d", idx[i]);
printf("\n");
 
return 0;
}

[edit] C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
 
template <typename T>
std::vector<size_t> equilibrium(T first, T last)
{
typedef typename std::iterator_traits<T>::value_type value_t;
 
value_t left = 0;
value_t right = std::accumulate(first, last, value_t(0));
std::vector<size_t> result;
 
for (size_t index = 0; first != last; ++first, ++index)
{
right -= *first;
if (left == right)
{
result.push_back(index);
}
left += *first;
}
return result;
}
 
template <typename T>
void print(const T& value)
{
std::cout << value << "\n";
}
 
int main()
{
const int data[] = { -7, 1, 5, 2, -4, 3, 0 };
 
std::vector<size_t> indices(equilibrium(data, data + 7));
 
std::for_each(indices.begin(), indices.end(), print<size_t>);
}
Output:
3
6

[edit] C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
static IEnumerable<int> EquilibriumIndices(IEnumerable<int> sequence)
{
var left = 0;
var right = sequence.Sum();
var index = 0;
foreach (var element in sequence)
{
right -= element;
if (left == right)
{
yield return index;
}
left += element;
index++;
}
}
 
static void Main()
{
foreach (var index in EquilibriumIndices(new[] { -7, 1, 5, 2, -4, 3, 0 }))
{
Console.WriteLine(index);
}
}
}
Output:
3
6

[edit] Clojure

Translation of: Ocaml
(defn equilibrium [lst]
(loop [acc '(), i 0, left 0, right (apply + lst), lst lst]
(if (empty? lst)
(reverse acc)
(let [[x & xs] lst
right (- right x)
acc (if (= left right) (cons i acc) acc)]
(recur acc (inc i) (+ left x) right xs)))))
Output:
> (equilibrium [-7, 1, 5, 2, -4, 3, 0])
(3 6)

[edit] Common Lisp

(defun dflt-on-nil (v dflt)
(if v v dflt))
 
(defun eq-index (v)
(do*
((stack nil)
(i 0 (+ 1 i))
(rest v (cdr rest))
(lsum 0)
(rsum (apply #'+ (cdr v))))
;; Reverse here is not strictly necessary
((null rest) (reverse stack))
(if (eql lsum rsum) (push i stack))
(setf lsum (+ lsum (car rest)))
(setf rsum (- rsum (dflt-on-nil (cadr rest) 0)))))

Output:

(eq-index '(-7 1 5 2 -4 3 0))
(3 6)

[edit] D

[edit] More Functional Style

import std.stdio, std.algorithm, std.range, std.functional;
 
auto equilibrium(Range)(Range r) pure nothrow {
return r.length.iota.filter!(i => r[0..i].sum == r[i+1 .. $].sum);
}
 
void main() {
[-7, 1, 5, 2, -4, 3, 0].equilibrium.writeln;
}
Output:
[3, 6]

[edit] Less Functional Style

Translation of: PHP

Same output.

import std.stdio, std.algorithm;
 
size_t[] equilibrium(T)(in T[] items) @safe pure nothrow {
size_t[] result;
T left = 0, right = items.sum;
 
foreach (immutable i, e; items) {
right -= e;
if (right == left)
result ~= i;
left += e;
}
return result;
}
 
void main() {
[-7, 1, 5, 2, -4, 3, 0].equilibrium.writeln;
}

[edit] Euphoria

function equilibrium(sequence s)
integer lower_sum, higher_sum
sequence indices
lower_sum = 0
higher_sum = 0
for i = 1 to length(s) do
higher_sum += s[i]
end for
indices = {}
for i = 1 to length(s) do
higher_sum -= s[i]
if lower_sum = higher_sum then
indices &= i
end if
lower_sum += s[i]
end for
return indices
end function
 
? equilibrium({-7,1,5,2,-4,3,0})
Output:

(Remember that indices are 1-based in Euphoria)

{4,7}

[edit] Factor

Executed in the listener. Note that accum-left and accum-right have different outputs than accumulate as they drop the final result.

USE: math.vectors
: accum-left ( seq id quot -- seq ) accumulate nip ; inline
: accum-right ( seq id quot -- seq ) [ <reversed> ] 2dip accum-left <reversed> ; inline
: equilibrium-indices ( seq -- inds )
0 [ + ] [ accum-left ] [ accum-right ] 3bi [ = ] 2map
V{ } swap dup length iota [ [ suffix ] curry [ ] if ] 2each ;
Output:
( scratchpad ) { -7 1 5 2 -4 3 0 } equilibrium-indices .
V{ 3 6 }

[edit] Fortran

Works with: Fortran version 90 and later

Array indices are 1-based.

program Equilibrium
implicit none
 
integer :: array(7) = (/ -7, 1, 5, 2, -4, 3, 0 /)
 
call equil_index(array)
 
contains
 
subroutine equil_index(a)
integer, intent(in) :: a(:)
integer :: i
 
do i = 1, size(a)
if(sum(a(1:i-1)) == sum(a(i+1:size(a)))) write(*,*) i
end do
 
end subroutine
end program

[edit] Go

package main
 
import (
"fmt"
"math/rand"
"time"
)
 
func main() {
fmt.Println(ex([]int32{-7, 1, 5, 2, -4, 3, 0}))
 
// sequence of 1,000,000 random numbers, with values
// chosen so that it will be likely to have a couple
// of equalibrium indexes.
rand.Seed(time.Now().UnixNano())
verylong := make([]int32, 1e6)
for i := range verylong {
verylong[i] = rand.Int31n(1001) - 500
}
fmt.Println(ex(verylong))
}
 
func ex(s []int32) (eq []int) {
var r, l int64
for _, el := range s {
r += int64(el)
}
for i, el := range s {
r -= int64(el)
if l == r {
eq = append(eq, i)
}
l += int64(el)
}
return
}
Output:
[3 6]
[145125 947872]

[edit] Haskell

import Data.List
import Control.Monad
import Control.Arrow
import System.Random
 
equilibr xs = elemIndices True. map (uncurry((.sum).(==). sum)).
takeWhile(not.null.snd) $ map (flip (liftM2 (&&&) take (drop. pred)) xs) [1..]
 
langeSliert =
replicateM 2000 (randomRIO (-15,15) :: IO Int)
>>= print. equilibr

Small example

*Main> equilibr [-7, 1, 5, 2, -4, 3, 0]
[3,6]

Long random list in langeSliert (several tries for this one)

*Main> langeSliert
[231,245,259,265,382,1480,1611,1612]

[edit] Icon and Unicon

procedure main(arglist)
L := if *arglist > 0 then arglist else [-7, 1, 5, 2, -4, 3, 0] # command line args or default
every writes( "equilibrium indicies of [ " | (!L ||" ") | "] = " | (eqindex(L)||" ") | "\n" )
end
 
procedure eqindex(L) # generate equilibrium points in a list L or fail
local s,l,i
 
every (s := 0, i := !L) do
s +:= numeric(i) | fail # sum and validate
 
every (l := 0, i := 1 to *L) do {
if l = (s-L[i])/2 then suspend i
l +:= L[i] # sum of left side
}
end
Output:
equilibrium indicies of [ -7 1 5 2 -4 3 0 ] = 4 7

[edit] J

equilidx=: +/\ I.@:= +/\.
Example use:
   equilidx _7 1 5 2 _4 3 0
3 6

[edit] Java

Works with: Java version 1.5+
 
public class Equlibrium {
public static void main(String[] args) {
int[] sequence = {-7, 1, 5, 2, -4, 3, 0};
equlibrium_indices(sequence);
}
 
public static void equlibrium_indices(int[] sequence){
//find total sum
int totalSum = 0;
for (int n : sequence) {
totalSum += n;
}
//compare running sum to remaining sum to find equlibrium indices
int runningSum = 0;
for (int i = 0; i < sequence.length; i++) {
int n = sequence[i];
if (totalSum - runningSum - n == runningSum) {
System.out.println(i);
}
runningSum += n;
}
}
}
 
Output:
3
6

[edit] K

   f:{&{(+/y# x)=+/(y+1)_x}[x]'!#x}
 
f -7 1 5 2 -4 3 0
3 6
 
f 2 4 6
!0
 
f 2 9 2
,1
 
f 1 -1 1 -1 1 -1 1
0 1 2 3 4 5 6

[edit] Liberty BASIC

 
a(0)=-7
a(1)=1
a(2)=5
a(3)=2
a(4)=-4
a(5)=3
a(6)=0
 
print "EQ Indices are ";EQindex$("a",0,6)
 
wait
 
function EQindex$(b$,mini,maxi)
if mini>=maxi then exit function
sum=0
for i = mini to maxi
sum=sum+eval(b$;"(";i;")")
next
sumA=0:sumB=sum
for i = mini to maxi
sumB = sumB - eval(b$;"(";i;")")
if sumA=sumB then EQindex$=EQindex$+str$(i)+", "
sumA = sumA + eval(b$;"(";i;")")
next
if len(EQindex$)>0 then EQindex$=mid$(EQindex$, 1, len(EQindex$)-2) 'remove last ", "
end function
 

Output:

EQ Indices are 3, 6 

[edit]

to equilibrium.iter :i :before :after :tail :ret
if equal? :before :after [make "ret lput :i :ret]
if empty? butfirst :tail [output :ret]
output equilibrium.iter :i+1 (:before+first :tail) (:after-first butfirst :tail) (butfirst :tail) :ret
end
to equilibrium.index :list
output equilibrium.iter 1 0 (apply "sum butfirst :list) :list []
end
 
show equilibrium_index [-7 1 5 2 -4 3 0]  ; [4 7]

[edit] Mathematica

Mathematica indexes are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays.

equilibriumIndex[data_]:=Reap[
Do[If[Total[data[[;; n - 1]]] == Total[data[[n + 1 ;;]]],Sow[n]],
{n, Length[data]}]][[2, 1]]
Usage:
equilibriumIndex[{-7 , 1, 5 , 2, -4 , 3, 0}]
{4, 7}

[edit] MATLAB

MATLAB arrays are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays.

function indicies = equilibriumIndex(list)
 
indicies = [];
 
for i = (1:numel(list))
if ( sum(-list(1:i)) == sum(-list(i:end)) )
indicies = [indicies i];
end
end
 
end
Output:
>> equilibriumIndex([-7 1 5 2 -4 3 0])
 
ans =
 
4 7

[edit] NetRexx

Translation of: Java
/* NetRexx */
options replace format comments java crossref symbols nobinary
 
numeric digits 20
runSample(arg)
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- @see http://www.geeksforgeeks.org/equilibrium-index-of-an-array/
method equilibriumIndex(sequence) private static
es = ''
loop ix = 1 to sequence.words()
sum = 0
loop jx = 1 to sequence.words()
if jx < ix then sum = sum + sequence.word(jx)
if jx > ix then sum = sum - sequence.word(jx)
end jx
if sum = 0 then es = es ix
end ix
return es
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
-- Note: A Rexx object based list of "words" starts at index 1
sequences = [ -
'-7 1 5 2 -4 3 0', - -- 4 7
' 2 4 6' , - -- (no equilibrium point)
' 0 2 4 0 6 0' , - -- 4
' 2 9 2' , - -- 2
' 1 -1 1 -1 1 -1 1' - -- 1 2 3 4 5 6 7
]
loop sequence over sequences
say 'For sequence "'sequence.space(1, ',')'" the equilibrium indices are: \-'
say '"'equilibriumIndex(sequence).space(1, ',')'"'
end sequence
return
 
 
Output:
For sequence "-7,1,5,2,-4,3,0" the equilibrium indices are: "4,7"
For sequence "2,4,6" the equilibrium indices are: ""
For sequence "0,2,4,0,6,0" the equilibrium indices are: "4"
For sequence "2,9,2" the equilibrium indices are: "2"
For sequence "1,-1,1,-1,1,-1,1" the equilibrium indices are: "1,2,3,4,5,6,7"

[edit] OCaml

let lst = [ -7; 1; 5; 2; -4; 3; 0 ]
let sum = List.fold_left ( + ) 0 lst
 
let () =
let rec aux acc i left right = function
| x::xs ->
let right = right - x in
let acc = if left = right then i::acc else acc in
aux acc (succ i) (left + x) right xs
| [] -> List.rev acc
in
let res = aux [] 0 0 sum lst in
print_string "Results:";
List.iter (Printf.printf " %d") res;
print_newline()

[edit] PARI/GP

This uses 1-based vectors instead of 0-based arrays; subtract 1 from each index if you prefer the other style.

equilib(v)={
my(a=sum(i=2,#v,v[i]),b=0,u=[]);
for(i=1,#v-1,
if(a==b, u=concat(u,i));
b+=v[i];
a-=v[i+1]
);
if(b,u,concat(u,#v))
};

[edit] Pascal

Program EquilibriumIndexDemo(output);
 
function ArraySum(list: array of integer; first, last: integer): integer;
var
i: integer;
begin
ArraySum := 0;
for i := first to last do // not taken if first > last
ArraySum := ArraySum + list[i];
end;
 
procedure EquilibriumIndex(list: array of integer; offset: integer);
var
i: integer;
begin
for i := low(list) to high(list) do
if ArraySum(list, low(list), i-1) = ArraySum(list, i+1, high(list)) then
write(offset + i:3);
end;
 
var
{** The base index of the array is fully taken care off and can be any number. **}
numbers: array [1..7] of integer = (-7, 1, 5, 2, -4, 3, 0);
i: integer;
 
begin
write('List of numbers: ');
for i := low(numbers) to high(numbers) do
write(numbers[i]:3);
writeln;
write('Equilibirum indices: ');
EquilibriumIndex(numbers, low(numbers));
writeln;
end.
Output:
:> ./EquilibriumIndex
List of numbers:  -7  1  5  2 -4  3  0
Equilibirum indices:   4  7

[edit] Perl

Translation of: Perl 6
sub eq_index {
my ( $i, $sum, %sums ) = ( 0, 0 );
 
for (@_) {
push @{ $sums{ $sum * 2 + $_ } }, $i++;
$sum += $_;
}
 
return join ' ', @{ $sums{$sum} || [] }, "\n";
}
 
print eq_index qw( -7 1 5 2 -4 3 0 ); # 3 6
print eq_index qw( 2 4 6 ); # (no eq point)
print eq_index qw( 2 9 2 ); # 1
print eq_index qw( 1 -1 1 -1 1 -1 1 ); # 0 1 2 3 4 5 6

[edit] Perl 6

sub equilibrium_index(@list) {
my ($left,$right) = 0, [+] @list;
 
gather for @list.kv -> $i, $x {
$right -= $x;
take $i if $left == $right;
$left += $x;
}
}
 
my @list = -7, 1, 5, 2, -4, 3, 0;
.say for equilibrium_index(@list);

And here's an FP solution that manages to remain O(n):

sub equilibrium_index(@list) {
my @a := [\+] @list;
my @b := reverse [\+] reverse @list;
^@list Zxx (@a »==« @b);
}

The [\+] is a reduction that returns a list of partial results. The »==« is a vectorized equality comparison; it returns a vector of true and false. The Zxx is a zip with the list replication operator, so we return only the elements of the left list where the right list is true (which is taken to mean 1 here). And the ^@list is just shorthand for 0 ..^ @list. We could just as easily have used @list.keys there.

[edit] Single-pass solution

The task can be restated in a way that removes the "right side" from the calculation.

C is the current element,
L is the sum of elements left of C,
R is the sum of elements right of C,
S is the sum of the entire list.

By definition, L + C + R == S for any choice of C, and L == R for any C that is an equilibrium point.
Therefore (by substituting L for R), L + C + L == S at all equilibrium points.
Restated, 2L + C == S.

# Original example, with expanded calculations:
0 1 2 3 4 5 6 # Index
-7 1 5 2 -4 3 0 # C (Value at index)
0 -7 -6 -1 1 -3 0 # L (Sum of left)
-7 -13 -7 0 -2 -3 0 # 2L+C

If we build a hash as we walk the list, with 2L+C as hash keys, and arrays of C-indexes as hash values, we get:

{
-7 => [ 0, 2 ],
-13 => [ 1 ],
0 => [ 3, 6 ],
-2 => [ 4 ],
-3 => [ 5 ],
}

After we have finished walking the list, we will have the sum (S), which we look up in the hash. Here S=0, so the equilibrium points are 3 and 6.

Note: In the code below, it is more convenient to calculate 2L+C *after* L has already been incremented by C; the calculation is simply 2L-C, because each L has an extra C in it. 2(L-C)+C == 2L-C.

sub eq_index ( *@list ) {
my $sum = 0;
 
my %h = @list.keys.classify: {
$sum += @list[$_];
$sum * 2 - @list[$_];
};
 
return %h{$sum} // [];
}
 
say eq_index < -7 1 5 2 -4 3 0 >; # 3 6
say eq_index < 2 4 6 >; # (no eq point)
say eq_index < 2 9 2 >; # 1
say eq_index < 1 -1 1 -1 1 -1 1 >; # 0 1 2 3 4 5 6

The .classify method creates a hash, with its code block's return value as key. Each hash value is an Array of all the inputs that returned that key.

We could have used .pairs instead of .keys to save the cost of @list lookups, but that would change each %h value to an Array of Pairs, which would complicate the return line.

[edit] PHP

<?php
$arr = array(-7, 1, 5, 2, -4, 3, 0);
 
function getEquilibriums($arr) {
$right = array_sum($arr);
$left = 0;
$equilibriums = array();
foreach($arr as $key => $value){
$right -= $value;
if($left == $right) $equilibriums[] = $key;
$left += $value;
}
return $equilibriums;
}
 
echo "# results:\n";
foreach (getEquilibriums($arr) as $r) echo "$r, ";
?>
Output:
# results:
3, 6,

[edit] PicoLisp

(de equilibria (Lst)
(make
(let Sum 0
(for ((I . L) Lst L (cdr L))
(and (= Sum (sum prog (cdr L))) (link I))
(inc 'Sum (car L)) ) ) ) )
Output:
: (equilibria (-7 1 5 2 -4 3 0))
-> (4 7)

: (equilibria (make (do 10000 (link (rand -10 10)))))
-> (4091 6174 6198 7104 7112 7754)

[edit] PureBasic

Translation of: Java
If OpenConsole()
Define i, c=CountProgramParameters()-1
For i=0 To c
Define j, LSum=0, RSum=0
For j=0 To c
If j<i
LSum+Val(ProgramParameter(j))
ElseIf j>i
RSum+Val(ProgramParameter(j))
EndIf
Next j
If LSum=RSum: PrintN(Str(i)): EndIf
Next i
EndIf
Output:
> Equilibrium.exe -7 1 5 2 -4 3 0
3
6

[edit] Python

[edit] Two Pass

Uses an initial summation of the whole list then visits each item of the list adding it to the left-hand sum (after a delay); and subtracting the item from the right-hand sum. I think it should be quicker than algorithms that scan the list creating left and right sums for each index as it does ~2N add/subtractions rather than n*n.

def eqindex2Pass(data):
"Two pass"
suml, sumr, ddelayed = 0, sum(data), 0
for i, d in enumerate(data):
suml += ddelayed
sumr -= d
ddelayed = d
if suml == sumr:
yield i

[edit] Multi Pass

This is the version that does more summations, but may be faster for some sizes of input as the sum function is implemented in C internally:

def eqindexMultiPass(data):
"Multi pass"
for i in range(len(data)):
suml, sumr = sum(data[:i]), sum(data[i+1:])
if suml == sumr:
yield i

Shorter alternative:

def eqindexMultiPass(s):
return [i for i in xrange(len(s)) if sum(s[:i]) == sum(s[i+1:])]
 
print eqindexMultiPass([-7, 1, 5, 2, -4, 3, 0])

[edit] One Pass

This routine would need careful evaluation against the two-pass solution above as, although it only runs through the data once, it may create a dict that is as long as the input data in its worst case of an input of say a simple 1, 2, 3, ... counting sequence.

from collections import defaultdict
 
def eqindex1Pass(data):
"One pass"
l, h = 0, defaultdict(list)
for i, c in enumerate(data):
l += c
h[l * 2 - c].append(i)
return h[l]

[edit] Tests

f = (eqindex2Pass, eqindexMultiPass, eqindex1Pass)
d = ([-7, 1, 5, 2, -4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1, -1, 1, -1, 1, -1, 1])
 
for data in d:
print("d = %r" % data)
for func in f:
print("  %16s(d) -> %r" % (func.__name__, list(func(data))))
Sample output:
d = [-7, 1, 5, 2, -4, 3, 0]
      eqindex2Pass(d) -> [3, 6]
  eqindexMultiPass(d) -> [3, 6]
      eqindex1Pass(d) -> [3, 6]
d = [2, 4, 6]
      eqindex2Pass(d) -> []
  eqindexMultiPass(d) -> []
      eqindex1Pass(d) -> []
d = [2, 9, 2]
      eqindex2Pass(d) -> [1]
  eqindexMultiPass(d) -> [1]
      eqindex1Pass(d) -> [1]
d = [1, -1, 1, -1, 1, -1, 1]
      eqindex2Pass(d) -> [0, 1, 2, 3, 4, 5, 6]
  eqindexMultiPass(d) -> [0, 1, 2, 3, 4, 5, 6]
      eqindex1Pass(d) -> [0, 1, 2, 3, 4, 5, 6]

[edit] Racket

 
#lang racket
(define (subsums xs)
(for/fold ([sums '()] [sum 0]) ([x xs])
(values (cons (+ x sum) sums)
(+ x sum))))
 
(define (equivilibrium xs)
(define-values (sums total) (subsums xs))
(for/list ([sum (reverse sums)]
[x xs]
[i (in-naturals)]
#:when (= (- sum x) (- total sum)))
i))
 
(equivilibrium '(-7 1 5 2 -4 3 0))
 

Output:

 
'(3 6)
 

[edit] REXX

/*REXX program finds the equalibrium index  for an numeric array (list).*/
parse arg x /*get the array's numbers. */
say ' array list: ' x /*echo the array list to screen. */
say /* ... and a blank line. */
k=0 /*needed for array list counter. */
do j=0 /*start J at 1 for 1-based arrays*/
k=k+1 /*bump counter of array numbers. */
_=word(x,k) /*get the number from the list. */
if _=='' then leave /*if null, then we are done. */
A.j=_ /*define the array element. */
end /*j*/
j=j-1 /*fudge DO index for the real cnt*/
ans=equalibriumIndex(0,j) /*calculate the equalibrium Index*/
@indexes='indices'; if ans==1 then @indexes='index' /*singular adj.*/
say 'equalibrium' @indexes": " ans /*show equalibrium index/indices.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────EQUALIBRIUMINDEX subroutine─────────*/
equalibriumIndex: procedure expose A. /*have the array A. be exposed.*/
parse arg start,many /*start is most likely 0 or 1 */
q= /*equalibrium indexes (so far). */
do e=start to many /*find various sums (top/bot). */
sumB=0 /*sum of bottom part of a list. */
do b=start to e-1 /*add the bottom part of a list. */
sumB=sumB + A.b /*add this array element to sumB.*/
end /*b*/
sumT=0 /*sum of top part of a list. */
do t=e+1 to many /*add the top part of a list. */
sumT=sumT + A.t /*add this array element to sumT.*/
end /*t*/
 
if sumB=sumT then q=q e /*if both sums equal, found one. */
end /*e*/
return strip(q) /*return the equalibrium list. */

output using the input: -7 1 5 2 -4 3 0

         array list:  -7 1 5 2 -4 3 0

equalibrium indices:  3 6

output using the input: 2 9 2

         array list:  2 9 2

equalibrium index:  1

output using the input: 1 -1 1 -1 1 -1 1

         array list:  1 -1 1 -1 1 -1 1

equalibrium indices:  0 1 2 3 4 5 6

[edit] Ruby

Works with: Ruby version 1.8.7
Functional Style
def eq_indices(list)
list.each_index.select do |i|
list[0...i].inject(0, :+) == list[i+1..-1].inject(0, :+)
end
end
Tail Recursion
  • This one would be good if Ruby did tail-call optimization (TCO).
  • MRI does not do TCO; so this function fails with a long list (by overflowing the call stack).
def eq_indices(list)
result = []
list.empty? and return result
final = list.size - 1
 
helper = lambda do |left, current, right, index|
left == right and result << index # Push index to result?
index == final and return # Terminate recursion?
new = list[index + 1]
helper.call(left + current, new, right - new, index + 1)
end
helper.call 0, list.first, list.drop(1).inject(:+), 0
result
end
Imperative Style (faster)
def eq_indices(list)
left, right = 0, list.inject(0, :+)
equilibrium_indices = []
 
list.each_with_index do |val, i|
right -= val
equilibrium_indices << i if right == left
left += val
end
 
equilibrium_indices
end
Test
indices = [
[-7, 1, 5, 2,-4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1,-1, 1,-1, 1,-1, 1]
]
indices.each do |x|
puts "%p => %p" % [x, eq_indices(x)]
end
Output:
[-7, 1, 5, 2, -4, 3, 0] => [3, 6]
[2, 4, 6] => []
[2, 9, 2] => [1]
[1, -1, 1, -1, 1, -1, 1] => [0, 1, 2, 3, 4, 5, 6]

[edit] Seed7

$ include "seed7_05.s7i";
 
const array integer: numList is [] (-7, 1, 5, 2, -4, 3, 0);
 
const func array integer: equilibriumIndex (in array integer: elements) is func
result
var array integer: indexList is 0 times 0;
local
var integer: element is 0;
var integer: index is 0;
var integer: sum is 0;
var integer: subSum is 0;
var integer: count is 0;
begin
indexList := length(elements) times 0;
for element range elements do
sum +:= element;
end for;
for element key index range elements do
if 2 * subSum + element = sum then
incr(count);
indexList[count] := index;
end if;
subSum +:= element;
end for;
indexList := indexList[.. count];
end func;
 
const proc: main is func
local
var array integer: indexList is 0 times 0;
var integer: element is 0;
begin
indexList := equilibriumIndex(numList);
write("Found:");
for element range indexList do
write(" " <& element);
end for;
writeln;
end func;
Output:
Found: 4 7

[edit] Tcl

proc listEquilibria {list} {
set after 0
foreach item $list {incr after $item}
set result {}
set idx 0
set before 0
foreach item $list {
incr after [expr {-$item}]
if {$after == $before} {
lappend result $idx
}
incr before $item
incr idx
}
return $result
}
Example of use
set testData {-7 1 5 2 -4 3 0}
puts Equilibria=[join [listEquilibria $testData] ", "]
Output:
Equilibria=3, 6

[edit] Ursala

#import std
#import int
 
edex = num@yK33ySPtK33xtS2px; ~&nS+ *~ ==+ ~~r sum:-0
 
#cast %nL
 
example = edex <-7,1,5,2,-4,3,0>
Output:
<3,6>

[edit] XPL0

code Ran=1, ChOut=8, IntOut=11;
def Size = 1_000_000;
int I, S, A(Size), Hi(Size), Lo(Size);
[for I:= 0 to Size-1 do A(I):= Ran(100) - 50;
S:= 0;
for I:= 0 to Size-1 do [S:= S+A(I); Lo(I):= S];
S:= 0;
for I:= Size-1 downto 0 do [S:= S+A(I); Hi(I):= S];
for I:= 0 to Size-1 do
if Lo(I) = Hi(I) then [IntOut(0, I); ChOut(0, ^ )];
]

Example output:

502910 504929 508168 

[edit] Yorick

Yorick arrays are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays.

func equilibrium_indices(A) {
return where(A(psum) == A(::-1)(psum)(::-1));
}
Example interactive usage:
> equilibrium_indices([-7, 1, 5, 2, -4, 3, 0])
[4,7]
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox