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:

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


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