fbpx

C++: Equilibrium Index

Bjarne-stroustrup
 

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.