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 regularly write solutions to programming problems that you may or may not find in technical job interviews. I also love to explain those solutions and answer questions. If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.