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]