TapeEquilibrium – Codility – Solution

Java solution to Codility TapeEquilibrium problem (Lesson 3 – Time Complexity) which scored 100%. The problem is to find the minimum sum of two sub-arrays.

The main strategy is to first calculate the sum of the entire array and then use a running sum for each array index to calculate the sum of both sub-arrays at each index.

[cc lang="java" escaped="true"]
package com.codility.lesson03.timecomplexity;

public class TapeEquilibrium {
	public int solution(int[] A) {
		long sumAllElements = 0;
		for(int i=0; i<A.length; i++) {
			sumAllElements += A[i];
		}
		
		int minDifference = Integer.MAX_VALUE;
		int currentDifference = Integer.MAX_VALUE;
		long sumFirstPart = 0;
		long sumSecondPart = 0;

		for(int p=0; p<A.length-1; p++) {
			sumFirstPart += A[p];
			sumSecondPart = sumAllElements - sumFirstPart;
			currentDifference = (int) Math.abs(sumFirstPart - sumSecondPart);
			minDifference = Math.min(currentDifference, minDifference);
		}
		return minDifference;
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson03.timecomplexity;

import org.testng.Assert;
import org.testng.annotations.*;

import com.codility.lesson03.timecomplexity.TapeEquilibrium;

public class TapeEquilibriumTests {
	private TapeEquilibrium solution;
	
	@BeforeTest
	public void setUp() {
		solution = new TapeEquilibrium();
	}

	@DataProvider(name = "test1")
	public Object [][] createData1() {
		return new Object [][] {
			new Object [] { new int [] {  3,    1,    2,    4,   3 }, 1 },
			new Object [] { new int [] { -3,    1,    2,   -4,   3 }, 1 },
			new Object [] { new int [] {        5,    2,    7,  10 }, 4 },
			new Object [] { new int [] {    -1000, 1000, -500, 990 }, 490 },
			new Object [] { new int [] {                    1,   2 }, 1 },
			new Object [] { new int [] {                  100, -25 }, 125 },
		};
	}

	@Test(dataProvider = "test1")
	public void verifySolution(int [] pA, int pExpectedMissingValue) {
		Assert.assertEquals(solution.solution(pA), pExpectedMissingValue);
	}
}
[/cc]