 # C++: Equilibrium Index 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.

```#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```

SOURCE

Content is available under GNU Free Documentation License 1.2.