«

»

Dev Technology Code Jam

Code-JamWednesday was the end of a pretty hectic sprint for a project we are developing, so instead of the usual code reviews that typically occur, we opted to take a couple of hours out of the day to bring the team together and solve an interesting problem. Dev Tech’er Sean Moon found a problem online and we split our Scrum team, and a few other developers who wanted free pizza, into two teams to work through and solve a mathematical problem using Java. The teams took two different approaches with only one of them coming up with a solution that was O(N), but both teams did a great job of working through the problem to find elegant and unique solutions. The discussion generated by reviewing the problem and the solution was well worth our time, and everyone learned a great deal about a few Java libraries, particularly java.util.stream’s IntStream.sum(), and the inefficiencies caused by map reduction for a problem like this. Thanks to all the participates for taking time out of your busy schedules to do some problem solving that really focused on creating mathematically optimized code. We’ll actually be applying some of our newly found knowledge to solve a data migration problem in the upcoming sprint!

The problem is below, and if you come up with a great solution, post it in the comments and we’ll let you know how you did.

The problem:

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.

A[0] + A[1] + … + A[P−1] = A[P+1] + … + A[N−2] + A[N−1].

Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

For example, consider the following array A consisting of N = 8 elements:

A[0] = -1 A[1] = 3 A[2] = -4 A[3] = 5 A[4] = 1 A[5] = -6 A[6] = 2 A[7] = 1

P = 1 is an equilibrium index of this array, because:

A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]

P = 3 is an equilibrium index of this array, because:

A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]

P = 7 is also an equilibrium index, because:

A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0

and there are no elements with indices greater than 7.

P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

Write a function:

class Solution { public int solution(int[] A); }

such that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

For example, given array A shown above, the function may return 1, 3 or 7, as explained above.

Assume that:

  • N is an integer within the range [0..100,000];
  • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
  • Elements of input arrays can be modified.