Java Solution to Codility’s Tape Equilibrium Problem

June 27, 2018

Hey Developer,

I am bringing you another high quality Java solution. This time, I am solving the Tape Equilibrium problem which can be found here.

My solution has runtime of O(N) and space complexity of O(N) as I am using a second array to solve the problem. The key to solving this problem is to think about it from a mathematical perspective before trying to write the code.

Explanation:

  1. Observe that no matter the value of P, the left summation and the right summation added together would equal to the total sum of all the elements in the array.
    • (A[0] + A[1] + … + A[P-1]) + (A[P] + A[P + 1] + … + A[N − 1]) == A[0] + A[1] + … + A[N-1]
  2. The second observation we can make is that if we know the total sum and the left sum then we can find the right sum by simple subtraction.
    • Right Sum = Total Sum – Left Sum

Below is the code for my Java solution.

class Solution {
 
	public int solution(int[] A) {
 
	// variable holding number of elements in A
	int N = A.length;
	// variable holding the total sum of the array
        int totalSum = 0;
        // variable holding the minimum difference that we are solving for
        int minDifference = Integer.MAX_VALUE;
        // O(N) space complexity array for holding the left summation (A[0] + A[1] + ... + A[P-1])
        // N-1 because the last element in the array is always part of right sum
        int [] leftSum = new int[N-1];
        // Element at index 0 is always part of the left sum
        leftSum[0] = A[0];
 
        // loop to calculate the total sum of A
	for (int i = 0; i < N; i++) {
                totalSum += A[i];
        }
 
	// loop to calculate all of the summations on the left side 
	// leftSum [0] = A[0]; leftSum[1] = A[0] + A[1]; leftSum[2] = A[0] + A[1] + A[2]; leftSum[P-1] = A[0] + A[1] + ... + A[P-1];
	for (int i = 1; i < N - 1; i++) {
	        leftSum[i] = leftSum[i-1] + A[i];
	}
 
	// variable to hold the current minimum difference as we are going through our loop
	int curr = 0;
	for (int i = 0; i < N - 1; i++) {
	        // calculating the minimum difference 
		curr = Math.abs(leftSum[i]-(totalSum-leftSum[i]));
		// if our minimum difference is bigger than our current minimum difference
		if (minDifference > curr) {
			// we update minDifference to accurately represent the minimum difference
			minDifference = curr;
		}
	}
 
	return minDifference;
    }
 
}