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.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}
}
TestNG test cases for this problem which all passed:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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);
}
}