Problem Statement

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

{\displaystyle A}

: 3   is an equilibrium index, because: 6   is also an equilibrium index, because: (sum of zero elements is zero) 7   is not an equilibrium index, because it is not a valid index of sequence

A

{\displaystyle A}

.

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

Let's start with the solution:

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