Given an array of integers, find an equilibrium index. An equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.
Edit 2017.07.01 Added three more example input & output. Fixed an off-by-one error in the Ruby implementation.
For example, consider the following array
Index 3 is an equilibrium index.
Index 6 is also an equilibrium index, because sum of zero elements is zero.
Index 7 is not an equilibrium index, because it is not a valid index of array
Input. The input file consists of one or more arrays, each on a single line. Each array consists of a sequence of integers, each pair separated by a single space. The input file is terminated by an EOF character. Consider the following example.
Output. The output file consists of an output line for each array in the input. Each output line consists of an equilibrium index (if any) or -1 when no equilibrium index exists. For example, the following output corresponds to the previous example input.
The proposed solution is
Just consider each position of a given array, from left to
right. Start with a variable
l for the left sum set to zero and a
r for the right sum set to the sum of all elements except the
first. Then, as you go from left to right, add the element that
becomes part of the left side to
l and subtract from
r the element that
leaves the right side. Return the current index when
r are equal.
Want to read more?
I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?