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*:

*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

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

#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

Content is available under GNU Free Documentation License 1.2.